\section{绪论}

\subsection{基本逻辑门及其底层电路}

逻辑高与逻辑低实际上对应于一定的电势范围\\
对于某逻辑值，一个数字元件输出的电势范围是其可接受的电势范围的子集\\
两者相差的范围称为\emph{噪声容限}，如图 \ref{fig:逻辑值所对应的电势范围、噪声容限} 所示

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.4\textwidth]{figures/逻辑高低的电压基础.png}
    \caption{逻辑值所对应的电势范围、噪声容限}
    \label{fig:逻辑值所对应的电势范围、噪声容限}
\end{figure}


\subsubsection{CMOS逻辑电路}
逻辑0/1 与电压的对应范围是可以设计的，通常可以选择5 V 的CMOS元件为例\\
$0\sim 1.5{\;\rm V}$ 对应逻辑0，而 $3.5\sim 5{\;\rm V}$ 对应逻辑1

NMOS与PMOS的电路符号与特性见图 

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.48\textwidth]{figures/n沟道MOS结构.png}
    \includegraphics[width=0.48\textwidth]{figures/p沟道MOS结构.png}
    \caption{NMOS与PMOS的电路符号与特性}
    \label{fig:NMOS与PMOS的电路符号与特性}
\end{figure}

NMOS: 栅极输入高电平源漏两极导通，栅极输入低电平断路\\
PMOS: 栅极输入高电平源漏两极断路，栅极输入低电平导通\\
两者的栅极电流始终为0


CMOS 基本反相器的电路组成如图 \ref{fig:COMS invertor} 所示
\begin{figure}[htbp]
    \centering
    \includegraphics[width=0.8\textwidth]{figures/cmos_invertor.png}
    \caption{COMS 反相器}
    \label{fig:COMS invertor}
\end{figure}

CMOS 与非门基本结构如图 \ref{fig:CMOS NAND Gate} 所示，分析：\\
只要输入有0则串联部分断路，并联部分导通，输出1\\
仅有输入全1时串联部分导通，并联部分断路，输出0

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.8\textwidth]{figures/cmos_nand_gate.png}
    \caption{CMOS 与非门}
    \label{fig:CMOS NAND Gate}
\end{figure}

CMOS 或非门基本结构如图 \ref{fig:CMOS NOR Gate} 所示，分析：\\
只要输入有1则串联部分断路，并联部分导通，输出0\\
只有输入全0时串联部分导通，并联部分断路，输出1

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.8\textwidth]{figures/cmos_nor_gate.png}
    \caption{CMOS 或非门}
    \label{fig:CMOS NOR Gate}
\end{figure}

\begin{quote}
    便于制造的基本元件为：非、与非、或非。若要制造‘跟随器、与、或’则需要再级联非门
\end{quote}

多输入与非门、或非门可参见图 \ref{fig:CMOS三输入与非门} 构建
\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.8\textwidth]{figures/cmos_nand_3input_gate.png}
    \caption{CMOS三输入与非门}
    \label{fig:CMOS三输入与非门}
\end{figure}

\subsubsection{TTL与非门}
TODO


\section{数制与编码}

\subsection{机器数与数学数}
数学数：不定长度，可表示任意数字\\
机器数：固定长度，只是一定长度的、有顺序的序列\\
若要在机器上表示有符号数、实数等数学数字，需要选取一定的编码方案来将这些数学数映射到机器数

\begin{quote}
    机器数并不只是二进制数
\end{quote}

机器数只能表示有限范围的数字，若运算结果超出界限就会发生\emph{溢出}，通常是高位截断\\
例如对于2位十六进制机器数，表示范围为 $00\sim 99$，此时：
\begin{align*}
    &\mathtt{0x00-0x01=0xFF} &
    &\mathtt{0xFF+0x01=0x00}
\end{align*}

可以用数学数的运算来模拟机器数的溢出现象\\
只需将超界的数学数加减足够的机器数周期，使之回归机器数范围即可\\
例如对于2位十进制机器数，其回归周期为100
$$
\begin{aligned}
    58+62 &= 120 \\
    120-100&=20
\end{aligned}
\qquad\Longrightarrow\qquad 
\mathtt{
    58 + 62 = 20
}
$$

由此，可以将机器数序列首位相接成环，如图 \ref{fig:机器数环形排布与加减法运算} 所示

\subsubsection{二进制机器数的加减法}\label{sec:二进制机器数的加减法}
符号含义见表 \ref{tab:二进制加减法中的符号含义}
\begin{table}[htpb]
    \centering
    \caption{二进制加减法中的符号含义}
    \label{tab:二进制加减法中的符号含义}
    \begin{tabular}{cc|cc}
        \toprule 
        符号 & 含义 & 符号 & 含义\\
        \midrule
        $c_{\rm in}$ & 被低位进位     & $c_{\rm out}$ & 给高位进位 \\
        $b_{\rm in}$ & 被低位借位     & $b_{\rm out}$ & 从高位借位 \\
        \bottomrule
    \end{tabular}
\end{table}

机器数的加减法定义如图 \ref{fig:机器数环形排布与加减法运算} 所示，顺时针为加法，逆时针为减法
\begin{figure}[htpb]
    \centering
    \begin{tikzpicture}[scale=0.8]
        \draw (0,0) node {\small \kaishu 机器数加减运算};
        \draw[thick,black] (0,-2) arc(-90:-270:2);
        \draw[thick,black] (0, 2) arc( 90:-90 :2);
        \draw[thick,red ,-latex]   ( 60:3) arc( 60:  0:3);
        \draw[thick,blue,-latex]   (120:3) arc(120:180:3);
        \draw[red ] ( 30:3.2) node {$+$};
        \draw[blue] (150:3.2) node {$-$};
        \foreach \i in {0,...,15}
        {
            \draw (22.5*\i:1.9) -- (22.5*\i:2.1);
        }
        \node at (-22.5*0 +90:2.5) {\small\texttt{0000}};
        \node at (-22.5*1 +90:2.5) {\small\texttt{0001}};
        \node at (-22.5*2 +90:2.5) {\small\texttt{0010}};
        \node at (-22.5*3 +90:2.5) {\small\texttt{0011}};
        \node at (-22.5*4 +90:2.5) {\small\texttt{0100}};
        \node at (-22.5*5 +90:2.5) {\small\texttt{0101}};
        \node at (-22.5*6 +90:2.5) {\small\texttt{0110}};
        \node at (-22.5*7 +90:2.5) {\small\texttt{0111}};
        \node at (-22.5*8 +90:2.5) {\small\texttt{1000}};
        \node at (-22.5*9 +90:2.5) {\small\texttt{1001}};
        \node at (-22.5*10+90:2.5) {\small\texttt{1010}};
        \node at (-22.5*11+90:2.5) {\small\texttt{1011}};
        \node at (-22.5*12+90:2.5) {\small\texttt{1100}};
        \node at (-22.5*13+90:2.5) {\small\texttt{1101}};
        \node at (-22.5*14+90:2.5) {\small\texttt{1110}};
        \node at (-22.5*15+90:2.5) {\small\texttt{1111}};
    \end{tikzpicture}
    \caption{机器数环形排布与加减法运算}
    \label{fig:机器数环形排布与加减法运算}
\end{figure}

机器数的加法与一般数学整数的加法无异，只是要注意溢出\\
机器数的减法实际上可以利用溢出转化为加法，以2位十进制机器数为例：
\begin{align*}
    82 - 39 &= 82 - 39 + 100 = 82 + 61 &
    \mathtt{82-39} &= \mathtt{82+61}\\
                   &= 143 = 143-100=43 &
                   &= \mathtt{43}
\end{align*}
可见，2位十进制机器数中：减$\mathtt{39}$ $\Longleftrightarrow$ 加$\mathtt{61}$ \\
然而若要利用 $\mathtt{39}$ 通过机器数运算获得 $\mathtt{61}$ 仍然不容易\\
幸运的是，在$n$位二进制中这种转化十分容易，称为\emph{补码运算}
\begin{align*}
     &x-y  &
     &1010 - 0101 &
     &\mathtt{1010-0101}  \\
    =\;& x-y+2^n &
    =\;& 1010 - 0101 + 10000&
    =\;& \\
    =\;& x + [(2^n-1)-y]+1 &
    =\;& 1010 + [1111-0101] + 1&
    =\;& \\
    =\;& x + y' +1 &
    =\;& 1010 + 1010 + 1 &
    =\;& \mathtt{1010 + 1010 + 1} \\
     \;& &
    =\;&1010+1011 &
    =\;& \\
     \;& &
    =\;& 10101 &
    =\;& \\
     \;& &
    =\;& 0101 &
    =\;& \texttt{0101}
\end{align*}
可见，二进制机器数的减法通过将减数\emph{按位取反加1}转化为加法\\
另外，上述步骤的正确性与 $x$ 与 $y$ 之间的大小关系无关

事实上，二进制计算机运行机器数减法的步骤如下：
\begin{enum}
    \item 减数$y$按位取反成为 $y'$
    \item 被减数 $x$ 与 $y'$ 做机器数加法，最低位 $c_{\rm in}$ 置 $\mathtt{1}$
\end{enum}

\begin{quote}
    对计算机而言，$x-y = x + (-y)$ 并不是一个显然的结论\\
    减法运算中的减号存在于机器指令中（通常被转化为取反、加法）\\
    求相反数中的负号则需要依照有符号数的编码规则来转化编码\\
    对机器数本身并无相反数的定义
\end{quote}

\subsubsection{补码运算的性质}
用上标 ${}^{\rm c}$ 表示机器数的补码运算，则对于 $n$ 位二进制机器数： 
$$
\mathtt{x^{\rm c}} = (2^n-1) - x + 1 = \mathtt{x'+1}
$$

补码运算两次就会回到原数，即 $\mathtt{x^{\rm cc}=x}$，因此 $\mathtt{x-y^{\rm c} = x + y}$
$$
(2^n-1) - \Big[ (2^n-1) - x + 1 \Big] +1 = 2^n -1 - 2^n + 1 + x -1 +1 = x
$$

补码之和 = 和之补码，即$\mathtt{x^{\rm c} + y^{\rm c} = (x+y)^{\rm c}}$：
$$
\Big[(2^n-1) - x + 1\Big] + \Big[(2^n-1) - y + 1\Big] = 2^n + \Big[(2^n-1) - (x+y) + 1\Big] = \Big[(2^n-1) - (x+y) + 1\Big]
$$

在如图 \ref{fig:机器数环形排布与加减法运算} 所示机器数环上，补码运算表示取 $x$ 关于纵轴对称的数字\\
可以由 $\mathtt{0-x} = \mathtt{0+x^{\rm c}}$ 得知这一点


\subsection{编码的基本概念}
编码：从原域向编码域的一一映射，从而可以用编码域中的元素代表原域中的对应元素\\
对于计算机，常用机器数来作为码位数字，来编码一定范围的数学整数、数学实数、文字字符等

一些编码方案可以将被编码物之间的运算与码位数字之间的机器数运算一一对应\\
从而可以用计算机来处理被编码物之间的运算关系

%例如，被编码物 $A,B,C$ 的编码分别为机器数 $\mathtt{a,b,c}$\\
%$A,B,C$ 之间有一种运算使得 $A\oplus B=C$，而编码数字之间恰好有机器数加法关系$\mathtt{a+b=c}$\\
%则这种编码方案可以将现实中的运算 $\oplus$ 映射为简易的机器数加法 $+$，从而实现自动化运算

%\begin{quote}
%    在任何编码方案下都必须保证被编码物的运算结果不超编码界\\
%    否则不可能保证编码域中的机器运算仍正确对应原域中的运算
%\end{quote}

下面首先处理数学整数的编码与运算\\
注意，任何数学数运算都不能超过被编码的范围，否则给出的一定是数学上错误的结果

%\begin{quote}
%非负的数学整数称为无符号整数\\
%正负均有的数学整数被称为有符号整数
%\end{quote}

%\subsection{Addition and Subtraction}
%
%\begin{center}
%\begin{tabular}{|ccc|cc|cc|}
%    \hline
%    c-in/b-in & X & Y & c-out & S & b-out & D\\
%    \hline
%    0 & 0 & 0 & 0 & 0 & 0 & 0 \\
%    \hline
%    0 & 0 & 1 & 0 & 1 & 1 & 1 \\
%    \hline
%    0 & 1 & 0 & 0 & 1 & 0 & 1 \\
%    \hline
%    0 & 1 & 1 & 1 & 0 & 0 & 0 \\
%    \hline
%    1 & 0 & 0 & 0 & 1 & 1 & 1 \\
%    \hline
%    1 & 0 & 1 & 1 & 0 & 1 & 0 \\
%    \hline
%    1 & 1 & 0 & 1 & 0 & 0 & 0 \\
%    \hline
%    1 & 1 & 1 & 1 & 1 & 1 & 1 \\
%    \hline
%\end{tabular}
%\end{center}

\subsection{无符号数学整数的编码与运算}
\subsubsection{编码与编码界}

无符号数学整数可以直接编码为等值的机器数\\
对于$n$位二进制机器数域，可以编码的数学数范围为 $0\sim 2^n-1$

\subsubsection{加减运算}
只要在数学域内运算结果不超编码界，机器数加减法就与无符号数加减法等价，也就是：
\begin{enum}
    \item 按照编码方案将数学数编码为机器数
    \item 按照要求对两个机器数做加减法
    \item 对运算结果按照编码方案解码为数学数
    \item 如果数学上正确的运算结果在编码域内，则上述过程给出的结果是正确的
\end{enum}

如上结论从图 \ref{fig:二进制机器数加减法循环关系图示} 上看是显然的\\
除非加减法操作越过了虚线段，运算结果在数学上一定是正确的

\begin{quote}
    这种证明方式只适用于不将减法通过补码运算转化为加法的情况\\
    但这种转化在结果上是等价的，因此可以确定运算结果的正确性\\
    只是采用补码运算后不能以此方式判断运算超界
\end{quote}

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.7\textwidth]{figures/二进制无符号数加减法图示.png}
    \caption{无符号数加减法对应的机器数运算}
    \label{fig:二进制机器数加减法循环关系图示}
\end{figure}

\subsubsection{加减法超界检测}
当且仅当无符号数运算结果超出编码界时，机器数运算溢出导致结果在数学上错误

对于无符号数加法来说，运算超界等价于机器数向上溢出\\
当 $x+y<  2^n$ 时运算正确，机器数运算最高位 $c_{\rm out}=0$\\
当 $x+y\ge2^n$ 时运算超界，机器数运算最高位 $c_{\rm out}=1$

对于无符号数减法来说，被转化为加法：$x-y=x+y'+1=x+(2^n-y)$\\
当 $x\ge y$ 时运算正确，机器数加法 $\mathtt{x+y'+1}=x+2^n-y\ge2^n$，因此 $c_{\rm out}=1$\\
当 $x<   y$ 时运算超界，机器数加法 $\mathtt{x+y'+1}=x+2^n-y<2^n$，因此$c_{\rm out}=0$

\begin{quote}
    CPU中有\texttt{Carry flag}与\texttt{Overflow flag} 两种状态位，进行机器数加减法时\textbf{同时}更新两者\\
    若此机器数运算表示无符号数学运算，则检测 \texttt{Carry flag}    以确定结果在数学上是否正确\\
    若此机器数运算表示有符号数学运算，则检测 \texttt{Overflow flag} 以确定结果在数学上是否正确
\end{quote}

\begin{quote}
    （\textbf{不太确定}）依据\href{https://en.wikipedia.org/wiki/Carry_flag#Vs._borrow_flag}{维基百科}及其引用的资料\\
    在进行机器数加法时，\texttt{Carry flag} 的定义是明确的\\
    最高位 $c_{\rm out}=1$ 时 \texttt{Carry flag} 置1，说明运算错误

    在进行机器数减法时，不同CPU架构对 \texttt{Carry flag} 的处理不同\\
    1) 视为 \texttt{Borrow flag}，最高位有借位则置1，则 \texttt{Carry flag=1} 说明运算错误\\
    2) 依据 $\mathtt{x+y'+1}$ 来决定 \texttt{Carry flag}，则 \texttt{Carry flag=0} 说明运算错误
\end{quote}

%对于无符号数减法来说，由于转化为加法时利用了溢出，最高位 $b_{\rm out}=1$ 并不能证明运算超界\\
%{\kaishu \color{red} 咋玩？图中包含了虚线的那一段圆弧所对应的减法结果是溢出的}
%
%\begin{tikzpicture}
%    \draw[thick,red ] ( 60:2) arc(60:-30:2);
%    \draw[thick,blue] (-30:2) arc(-30:-247.5:2);
%    \draw[thick,blue,dashed] (-247.5:2) arc(-247.5:-270:2);
%    \draw[thick,blue] (-270:2) arc(-270:-300:2);
%    \draw (-247.5:1.9) -- (-247.5:2.1);
%    \draw (-270:1.9) -- (-270:2.1);
%    \fill[black] (-30:2) node[right]{$x$} circle[radius=0.05];
%    \fill[black] ( 60:2) node[right]{$y$} circle[radius=0.05];
%    \node at (0,+0.2) {${\color{red} x-y}$};
%    \node at (0,-0.2) {${\color{blue}y-x}$};
%\end{tikzpicture}

%\begin{tikzpicture}
%    \draw[thick,blue] (0,-3) arc(-90:-270:3);
%    \draw[thick,red ] (0, 3) arc( 90:-90 :3);
%    \foreach \i in {0,...,15}
%    {
%        \draw (22.5*\i:2.9) -- (22.5*\i:3.1);
%    }
%    \node at (-22.5*0 +90:3.5) {0000};
%    \node at (-22.5*1 +90:3.5) {0001};
%    \node at (-22.5*2 +90:3.5) {0010};
%    \node at (-22.5*3 +90:3.5) {0011};
%    \node at (-22.5*4 +90:3.5) {0100};
%    \node at (-22.5*5 +90:3.5) {0101};
%    \node at (-22.5*6 +90:3.5) {0110};
%    \node at (-22.5*7 +90:3.5) {0111};
%    \node at (-22.5*8 +90:3.5) {1000};
%    \node at (-22.5*9 +90:3.5) {1001};
%    \node at (-22.5*10+90:3.5) {1010};
%    \node at (-22.5*11+90:3.5) {1011};
%    \node at (-22.5*12+90:3.5) {1100};
%    \node at (-22.5*13+90:3.5) {1101};
%    \node at (-22.5*14+90:3.5) {1110};
%    \node at (-22.5*15+90:3.5) {1111};
%\end{tikzpicture}


%\subsubsection{二进制无符号数的减法运算}
%运算规则：略
%
%如图 \ref{fig:二进制无符号数的编码、加减法、溢出图示} 所示，顺时针为加法，逆时针为减法
%
%\begin{figure}[htpb]
%    \centering
%    \includegraphics[width=0.7\textwidth]{figures/二进制无符号数加减法图示.png}
%    \caption{二进制无符号数的编码、加减法、溢出图示}
%    \label{fig:二进制无符号数的编码、加减法、溢出图示}
%\end{figure}
%
%\begin{quote}
%    实际上计算机并不做无符号减法运算，而是借助类似有符号数中的补码方案，转化为无符号加法运算
%\end{quote}
%
%\subsubsection{无符号数加减法的溢出检测}
%在图 \ref{fig:二进制无符号数的编码、加减法、溢出图示} 中，若运算经过了虚线所在位置则溢出
%
%溢出检测：若最高位有进位或借位则有溢出
%
%\subsubsection{无符号减法转化为加法}
%
%利用机器数的溢出现象，可以将无符号减法转化为无符号加法\\
%例如对2位十进制数
%$$
%96 - 52 = 96-52+100=96+48=144=44
%$$


\subsection{有符号数学整数的编码与运算}
有符号数的加减法均可以转化为：探测符号+取相反数+无符号加减法

\subsubsection{原码数制 Signed-magnitude system}
绝对值 + 最高符号位 (Signed-bit)

二进制原码数制的特征：
\begin{enum}
    \item 数字0有两个编码
    \item 最高位为 $0$ 的是正数，最高位为 $1$ 的是负数
    \item 在加减运算中必须额外地处理符号位，视情况转化为无符号加减法并决定最终结果的符号位\\
          因此实质上必须对机器数加法器做出改造，形成有符号加法器
    %\item 原码减法可直接转化为原码加法，从而只需要实现原码加法器
    %\item 总结起来需要实现：编解码器（简单）、有符号加法器（复杂）
\end{enum}

\subsubsection{补码数制 Complement number system}

\paragraph{编码与编码界}
%在一节中给出了二进制机器数减转化为加的方法：补码运算\\
%通过将负号转化为减号，构建编码方案：
%\begin{align*}
%    (-x) = 0-x \Longrightarrow \texttt{x}^{\rm c}
%\end{align*}

考虑到负数 $-y$ 在加减法中的作用与 $2^n-y$ 无异，令 $-y$ 占用原先无符号数 $2^n-y$ 的码位，也就是：
\begin{enum}
    \item 对于正数，直接编码为等值的机器数
    \item 对于负数$(-x)$，以 $x$ 的等值机器数的补码 $\mathtt{x^{\rm c}}$作为 $(-x)$ 的编码
    \item 编码：范围内数学数都可通过加减机器数周期映射到机器数域内
    \item 解码：任何的机器数都可通过加减机器数周期映射到数学数域内
\end{enum}

对于编码范围的考量：
\begin{enum}
    \item 由于 $0$ 的存在，能够编码的正数与负数必然数量不相等，通常使得正数、负数的数量仅相差1
    \item 最终有争议的唯一机器数是正负数交接处的一个
    \item 观察已有正负数编码特征，发现负数最高位均为1，正数最高位均为0，而有争议码位最高位为1
    \item 编码中负数比正数多一个，编码范围 $-2^{n-1} \sim 2^{n-1}-1$
\end{enum}

\begin{quote}
    事实上机器数本就是成环的，无所谓起点终点\\
    有符号数补码编码与无符号数编码相比，只是对“在何处将环剪开”有所不同\\
    由此可以直接看到：只要不超界，机器数加减法与补码方案下有符号数加减法一一对应
\end{quote}

%\paragraph{进一步解释}
%以两位十进制数为例说明补码：\\
%现有码位 $00,01,\cdots,99$，要编码 $0$ 附近连续一百个正负数
%
%补码利用了固定宽度数的溢出特性，对于两位十进制数来说也就是百位以上数字无效\\
%用一般数学模拟固定宽度数的运算：可在运算过程中保留本该溢出的数位，在最终结果中再进行溢出即可
%
%以蓝色代表溢出位，以下运算成立：$-23={\color{blue}1}00-23=77$\\
%也就是说，在含溢出的两位十进制下 $77=-23$，自然可将 $77$ 作为数字 $-23$ 的编码\\
%实际上，对于两位十进制数，彼此相差 $100$ 的数学数字是没有差别的
%
%
%则编码方案如表 \ref{tab:两位十进制数的补码编码方案} 所示
%\begin{table}[htpb]
%    \centering
%    \caption{两位十进制数的补码编码方案}
%    \label{tab:两位十进制数的补码编码方案}
%    \begin{tabular}{|c|ccccc|c|ccccc|}
%        \hline
%        无符号码位 & $50 $ & $51 $ & $\cdots$ & $98$ & $99$ & $0$ & $1$ & $2$ & $\cdots$ & $48$ & $49$ \\
%        被编码数字 & $-50$ & $-49$ & $\cdots$ & $-2$ & $-1$ & $0$ & $1$ & $2$ & $\cdots$ & $48$ & $49$ \\
%        \hline \end{tabular}
%\end{table}

补码方案的特点：
\begin{enum}
    \item 数字 0 只有一个编码
    \item 最高位为 $0$ 的是正数，最高位为 $1$ 的是负数
    %\item 有符号加法运算转化为无符号加法运算（利用溢出）\\
    %      例如：两位十进制运算 $-1+(-2)=-3$ 被转化为 $98+99=197=97$
    %\item 有符号减法运算转化为与负数的加法，进而转化为无符号加法
    %\item 总结起来需要实现：编解码器（复杂）、加减法运算使用无符号加法器即可
    \item 利用了机器数加减运算特征，只要运算不超界，有符号加减法可以直接利用机器数加法器
\end{enum}

%然而稍后可以看到，对于二进制来说补码方案的编解码器并没有很复杂

\paragraph{加减运算}
如图 \ref{fig:二进制补码加减法图示} 中可以明显看出\\
只要在数学域内运算结果不超编码界，机器数加减法就与有符号数加减法等价，也就是：
\begin{enum}
    \item 按照编码方案将数学数编码为机器数
    \item 按照要求对两个机器数做加减法
    \item 对运算结果按照编码方案解码为数学数
    \item 如果数学上正确的运算结果在编码域内，则上述过程给出的结果是正确的
\end{enum}

%补码方案下有符号数的加减运算与码位数字的机器数加减运算一一对应，如表 \ref{tab:有符号数补码方案的加减法}\\
%要求数学运算结果不超过编码界

%\begin{table}[htpb]
%    \centering
%    \caption{有符号数补码方案的加减法}
%    \label{tab:有符号数补码方案的加减法}
%    \begin{tabular}{c|l|l}
%        \toprule
%        &数学数域 & 机器数域 \\ 
%        \midrule
%        ❶ & $y+x$ & $\mathtt{y+x = (y+x)}$\\
%        \midrule
%        \multirow{2}{*}{❷} &
%        $y+(-x) = y-x,\;y\ge x$ & $\mathtt{y+x^{\rm c}=(y-x)}$ \\
%        & $y+(-x) = -(x-y),\;y<x$ & $\mathtt{y+x^{\rm c}=(x+y^{\rm c})^{\rm c}=(x-y)^{\rm c}}$ \\
%        \midrule
%        ❸ &$y-x = y+(-x)$ 转化为❷ & $\mathtt{y-x = y+x^{\rm c}}$ 转化为❷\\
%        \midrule
%        ❹ &$y-(-x) = y+x$ & $\mathtt{y-x^{\rm c}=y+x^{\rm cc} = (y+x)}$\\
%        \midrule
%        ❺ & $(-y)+x=x+(-y)$ 转化为❷ & $\mathtt{y^{\rm c}+x = x+y^{\rm c}}$ 转化为❷\\
%        \midrule
%        ❻ &$(-y)+(-x) = -(y+x)$ & $\mathtt{y^{\rm c}+x^{\rm c}=(y+x)^{\rm c}}$\\
%        \midrule
%        ❼ &$(-y)-x = (-y)+(-x)$ 转化为❻ & $\mathtt{y^{\rm c}-x=y^{\rm c}+x^{\rm c}}$ 转化为❻\\
%        \midrule
%        ❽ &$(-y)-(-x) = x+(-y)$ 转化为❷ & $\mathtt{y^{\rm c}-x^{\rm c} = x + y^{\rm c}}$ 转化为❷ \\
%        \bottomrule
%    \end{tabular}
%\end{table}



\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.8\textwidth]{figures/二进制补码加减法图示.png}
    \caption{有符号数加减法对应的机器数运算}
    \label{fig:二进制补码加减法图示}
\end{figure}

\paragraph{二进制补码加减法的溢出检测}
%为在运算超界得到错误结果时及时发出警告，需要溢出检测
%由于补码方案利用了无符号数的溢出，不能仅凭最高位有进位认为运算溢出\\
%正确的溢出检测：在图 \ref{fig:二进制补码加减法图示} 中，如果运算越过虚线圆弧则溢出

对于加法，可以看到：\\
两个异号数字运算不可能溢出。两个同号数字运算可以溢出，且溢出结果一定为异号数字\\
可得到：若两个加数最高位相同，而运算结果的最高位与它们不同则溢出\\
等效为：若最高位得到的进位 $c_{\rm in}$ 与给出的进位 $c_{\rm out}$ 不相等，则溢出

对于减法，可以看到：\\
两个同号数字运算不可能溢出，两个异号数字运算可以溢出，且溢出结果与被减数的符号相异\\
可得到：被减数与取反后的减数最高位相同，而运算结果的最高位与它们不同则溢出\\
等效为：若最高位得到的进位 $c_{\rm in}$ 与给出的进位 $c_{\rm out}$ 不相等，则溢出

综上，只要最终的无符号加法运算结果最高位 $c_{\rm in}\ne c_{\rm out}$ 则两个补码数加减法运算溢出

\begin{quote}
    在进行机器数加减法后检测 \texttt{Overflow flag} 即可得知有符号数加减法结果是否在数学上正确
\end{quote}

%\begin{quote}
%    二进制的反码编码方案：正数的编码为其本身，负数的编码为其相反数的二进制串按位取反
%\end{quote}

\paragraph{固定宽度二进制的补码编解码器}
%对于一个要用 $2$ 位十进制编码的十进制负数 $-23$ 来说，其补码编码是 $(-23)+10^2$\\
%对于一个要用 $n$ 位二进制编码的二进制负数 $-x$ 来说，其补码编码是：
%$$
%2^n+(-x) = \big[(2^n-1) - x\big] + 1 
%$$
%
%可以注意到：
%\begin{enum}
%    \item $2^n-1$ 是 $n$ 位二进制正数且所有位全为 $1$
%    \item $x$ 是原数字的相反数，是一个 $n$ 位二进制正数
%    \item 上两者做差实际上相当于将 $x$ 视为 $n$ 位无符号二进制数并按位取反
%    \item 最终运算结果是：取原负数的相反数，视为无符号数字按位取反，再加 $1$
%    \item 从编码与数字的映射关系看，二进制补码的最高位为0的是正数，最高位为1的是负数
%\end{enum}
%

从补码运算性质可以得到 $n$ 位二进制的补码编解码器：
\begin{enum}
\item 编码正数：去除正号、化二进制、补足宽度
\item 编码负数：去除负号、化二进制、补足宽度、按位取反加1
\item 解码正数：探测最高位为0、化十进制、添加正号
\item 解码负数：探测最高位为1、按位取反加1、化十进制、添加负号
%      证明如下：对于负的二进制数 $-x$
%      $$
%      (2^n-1) - \Big[ (2^n-1) - x + 1 \Big] +1 = 2^n -1 - 2^n + 1 + x -1 +1 = x
%      $$
\end{enum}


%\begin{tikzpicture}
%    \draw[thick,red ] ( 60:2) arc(60:-30:2);
%    \draw[thick,blue] (-30:2) arc(-30:-247.5:2);
%    \draw[thick,blue,dashed] (-247.5:2) arc(-247.5:-270:2);
%    \draw[thick,blue] (-270:2) arc(-270:-300:2);
%    \draw (-247.5:1.9) -- (-247.5:2.1);
%    \draw (-270:1.9) -- (-270:2.1);
%    \fill[black] (-30:2) node[right]{$x$} circle[radius=0.05];
%    \fill[black] ( 60:2) node[right]{$y$} circle[radius=0.05];
%    \node at (0,+0.2) {${\color{red} x-y}$};
%    \node at (0,-0.2) {${\color{blue}y-x}$};
%\end{tikzpicture}

\paragraph{总结：机器数、无符号数、有符号数的加减运算}
如图 \ref{fig:机器数、无符号数、有符号数的加减运算} 所示，三者的加减运算对于计算机来说并无任何差别\\
所不同的只是编解码的方案以及超界检测
\begin{figure}[htpb]
    \centering
    \begin{tikzpicture}[scale=0.8]
        \draw (0,0) node {\small \kaishu 机器数加减运算};
        \draw[thick,black] (0,-2) arc(-90:-270:2);
        \draw[thick,black] (0, 2) arc( 90:-90 :2);
        \foreach \i in {0,...,15}
        {
            \draw (22.5*\i:1.9) -- (22.5*\i:2.1);
        }
        \node at (-22.5*0 +90:2.5) {\small\texttt{0000}};
        \node at (-22.5*1 +90:2.5) {\small\texttt{0001}};
        \node at (-22.5*2 +90:2.5) {\small\texttt{0010}};
        \node at (-22.5*3 +90:2.5) {\small\texttt{0011}};
        \node at (-22.5*4 +90:2.5) {\small\texttt{0100}};
        \node at (-22.5*5 +90:2.5) {\small\texttt{0101}};
        \node at (-22.5*6 +90:2.5) {\small\texttt{0110}};
        \node at (-22.5*7 +90:2.5) {\small\texttt{0111}};
        \node at (-22.5*8 +90:2.5) {\small\texttt{1000}};
        \node at (-22.5*9 +90:2.5) {\small\texttt{1001}};
        \node at (-22.5*10+90:2.5) {\small\texttt{1010}};
        \node at (-22.5*11+90:2.5) {\small\texttt{1011}};
        \node at (-22.5*12+90:2.5) {\small\texttt{1100}};
        \node at (-22.5*13+90:2.5) {\small\texttt{1101}};
        \node at (-22.5*14+90:2.5) {\small\texttt{1110}};
        \node at (-22.5*15+90:2.5) {\small\texttt{1111}};
    \end{tikzpicture}
    \begin{tikzpicture}[scale=0.8]
        \draw (0, 0.3) node {\small \kaishu 无符号数的};
        \draw (0,-0.3) node {\small \kaishu 机器数运算};
        \draw[thick,red] (0,-2) arc(-90:-247.5:2);
        \draw[thick,red] (0, 2) arc( 90:-90 :2);
        \draw[thick,red,dashed] (-247.5:2) arc(-247.5:-270:2);
        \foreach \i in {0,...,15}
        {
            \draw (22.5*\i:1.9) -- (22.5*\i:2.1);
        }
        \node at (-22.5*0 +90:2.5) {\small\texttt{0000}};
        \node at (-22.5*1 +90:2.5) {\small\texttt{0001}};
        \node at (-22.5*2 +90:2.5) {\small\texttt{0010}};
        \node at (-22.5*3 +90:2.5) {\small\texttt{0011}};
        \node at (-22.5*4 +90:2.5) {\small\texttt{0100}};
        \node at (-22.5*5 +90:2.5) {\small\texttt{0101}};
        \node at (-22.5*6 +90:2.5) {\small\texttt{0110}};
        \node at (-22.5*7 +90:2.5) {\small\texttt{0111}};
        \node at (-22.5*8 +90:2.5) {\small\texttt{1000}};
        \node at (-22.5*9 +90:2.5) {\small\texttt{1001}};
        \node at (-22.5*10+90:2.5) {\small\texttt{1010}};
        \node at (-22.5*11+90:2.5) {\small\texttt{1011}};
        \node at (-22.5*12+90:2.5) {\small\texttt{1100}};
        \node at (-22.5*13+90:2.5) {\small\texttt{1101}};
        \node at (-22.5*14+90:2.5) {\small\texttt{1110}};
        \node at (-22.5*15+90:2.5) {\small\texttt{1111}};
    \end{tikzpicture}
    \begin{tikzpicture}[scale=0.8]
        \draw (0, 0.3) node {\small \kaishu 有符号数的};
        \draw (0,-0.3) node {\small \kaishu 机器数运算};
        \draw[thick,blue] (0,-2) arc(-90:-270:2);
        \draw[thick,red ] (0, 2) arc( 90:-67.5 :2);
        \draw[thick,black,dashed] (-67.5:2) arc(-67.5:-90:2);
        \foreach \i in {0,...,15}
        {
            \draw (22.5*\i:1.9) -- (22.5*\i:2.1);
        }
        \node at (-22.5*0 +90:2.5) {\small\texttt{0000}};
        \node at (-22.5*1 +90:2.5) {\small\texttt{0001}};
        \node at (-22.5*2 +90:2.5) {\small\texttt{0010}};
        \node at (-22.5*3 +90:2.5) {\small\texttt{0011}};
        \node at (-22.5*4 +90:2.5) {\small\texttt{0100}};
        \node at (-22.5*5 +90:2.5) {\small\texttt{0101}};
        \node at (-22.5*6 +90:2.5) {\small\texttt{0110}};
        \node at (-22.5*7 +90:2.5) {\small\texttt{0111}};
        \node at (-22.5*8 +90:2.5) {\small\texttt{1000}};
        \node at (-22.5*9 +90:2.5) {\small\texttt{1001}};
        \node at (-22.5*10+90:2.5) {\small\texttt{1010}};
        \node at (-22.5*11+90:2.5) {\small\texttt{1011}};
        \node at (-22.5*12+90:2.5) {\small\texttt{1100}};
        \node at (-22.5*13+90:2.5) {\small\texttt{1101}};
        \node at (-22.5*14+90:2.5) {\small\texttt{1110}};
        \node at (-22.5*15+90:2.5) {\small\texttt{1111}};
    \end{tikzpicture}
    \caption{机器数、无符号数、有符号数的加减运算}
    \label{fig:机器数、无符号数、有符号数的加减运算}
\end{figure}

\subsection{用二进制编码十进制数(BCD)}
表 \ref{tab:用二进制编码十进制的编码方案} 中展示了用二进制编码一位无符号十进制数的编码方式\\
对于多位无符号十进制数，则将每位数字都按表转化为二进制数，按顺序拼接在一起即可\\
对于有符号十进制数，采用原码、反码、补码等方案编码为无符号十进制数，再编码为二进制数

\begin{table}[htpb]
    \centering
    \caption{几种用二进制编码无符号十进制的编码方案}
    \label{tab:用二进制编码十进制的编码方案}
    \includegraphics[width=0.7\textwidth]{figures/几种用二进制编码十进制的编码方案.png}
\end{table}

前三种都是用 4 位二进制表示1位十进制，均有6个无效码位
\begin{enum}
    \item BCD码也称8421码，四位二进制的权重分别固定为 $8,4,2,1$，是最常用方案
    \item 2421码也是有权码，四位二进制的权重分别固定为 $2,4,2,1$
    \item 余三码是无权码，是在BCD码的基础上二进制加3得到
\end{enum}

\begin{quote}
    实际上若将BCD编码写为16进制则很容易看出其编码的十进制数\\
    例如十进制数 96 的BCD编码即为 $\mathtt{0x96}$\\
    而含有16进制数 $\tt A\sim F$ 的数则是无效编码
\end{quote}

\begin{quote}
    对于 $0\sim 4$：2421码 = 8421码\\
    对于 $5\sim 9$：2421码 = 8421码 + 6
\end{quote}

\subsubsection{BCD码的加减法与溢出检测}
由于BCD码是无符号数编码，此处的加减法为无符号十进制加减法，但要用无符号二进制运算模拟

BCD加法：\\
将两个BCD码二进制相加，从最低位开始检测\\
若给出进位或落入非法区，则此位上的数字加6\\
对结果重复上述过程，直到最高位处理完毕

超界判断：在修正完毕后最高位给出进位


\subsection{可靠性编码 - Gray码}
在一次运算中，电路可能出现并不想要的中间过程。若中间过程被捕捉，可能产生错误\\
例如由001到010的过程中可能出现中间过程 011或000

提升可靠性：确保每个“+1”运算都只有一个二进制位反转，杜绝中间过程\\
三位二进制的格雷码编码表见表 \ref{tab:三位二进制的格雷码编码表} 

\begin{table}[htpb]
    \centering
    \caption{三位二进制的格雷码编码表}
    \label{tab:三位二进制的格雷码编码表}
    \includegraphics[width=0.4\textwidth]{figures/格雷码编码表.png}
\end{table}


\subsubsection{Binary 与 Gray 相互转化}
记$n$ 位二进制码和格雷码的每一位分别为：
$$
\begin{aligned}
    B &= B_{n-1}\cdots B_{i+1}B_i \cdots B_0\\
    G &= G_{n-1}\cdots G_{i+1}G_i \cdots G_0
\end{aligned}
$$

Binary to Gray：记$B_{n} = 0$
$$
G_i = B_{i+1} \oplus B_i
$$ 

Gray to Binary：
$$
\begin{aligned}
    B_{n-1} &= G_{n-1}\\
    B_{n-2} &= G_{n-1}\oplus G_{n-2}\\
    B_{n-3} &= G_{n-1}\oplus G_{n-1}\oplus G_{n-3}\\
    B_i     &= B_{i+1} \oplus G_i
\end{aligned}
$$

上述过程可用图 \ref{fig:格雷码和一般二进制码的互相转化} 展现，图中 $\oplus$ 代表异或运算
\begin{figure}[htpb]
    \centering
    \begin{tikzpicture}
        \node at (-0,1) {Bin\ };
        \node at (-0,0) {Gray};
        %\node (A) at (0,1) {$\color{blue}0$};
        \node (B) at (1,1) {$1$};
        \node (C) at (2,1) {$0$};
        \node (D) at (3,1) {$1$};
        \foreach \i in {1,2}{
            \draw[thick,blue,-latex] (\i  ,0.8) -- (\i+1,0.2);
            \draw[thick,blue,-latex] (\i+1,0.8) -- (\i+1,0.2);
            \node at (\i+0.83,0.5) {$\color{blue}\oplus$};
        }
            \draw[thick,blue,-latex] (0+1,0.8) -- (0+1,0.2);
            \node at (0+0.75,0.5) {$\color{blue}=$};
        \node at (1,0) {$1$};
        \node at (2,0) {$1$};
        \node at (3,0) {$1$};
    \end{tikzpicture}
    \hspace{2cm}
    \begin{tikzpicture}
        \node at (0,1) {Bin\ };
        \node at (0,0) {Gray};
        \node (B) at (1,1) {$1$};
        \node (C) at (2,1) {$0$};
        \node (D) at (3,1) {$1$};
        \draw[thick,blue,-latex] (1  ,0.2) -- (1  ,0.8);
        \foreach \i in {2,3}{
            \draw[thick,blue,-latex] (\i-0.8,1) -- (\i-0.1,1);
            \draw[thick,blue,-latex] (\i  ,0.2) -- (\i  ,0.8);
            \node at (\i-0.2,0.75) {$\color{blue}\oplus$};
        }
        \node at (0.75,0.5) {$\rm\color{blue}=$};
        \node at (1,0) {$1$};
        \node at (2,0) {$1$};
        \node at (3,0) {$1$};
    \end{tikzpicture}
    \caption{格雷码和一般二进制码的互相转化}
    \label{fig:格雷码和一般二进制码的互相转化}
\end{figure}

\subsection{校验码与纠错码}
对于两个编码数字，它们之间由差异的bit位个数称为两者之间的距离\\
若编码方案中合法码位之间的距离都至少为 $m$，则可以检测出所有的 $m-1$ 位差错

\subsubsection{奇偶校验码（检错码）}
使用1个bit位作为奇偶校验位，其值由数据位决定\\
偶校验位：使得使得整个编码串中 “1”的个数是偶数\\
奇校验位：使得使得整个编码串中 “1”的个数是奇数

\subsubsection{海明码（纠错码）}
给出了纠正任意长度数据的1位错误的纠错码，下面为 4bit 数据位的纠错方案：

8421海明码：可以纠正任意的1bit错误（4bit Data + 3bit Check）\\
$B_4B_3B_2{\color{blue}P_3}B_1{\color{blue}P_2P_1}$

发送端：生成Check位 $P_3,P_2,P_1$
\begin{align*}
    P_3 &= B_4 \oplus B_3 \oplus B_2\\
    P_2 &= B_4 \oplus B_3 \oplus B_1\\
    P_1 &= B_4 \oplus B_2 \oplus B_1
\end{align*}

接收端：计算并查表决定错误所在位置，取反即可纠错
\begin{align*}
    S_3 &= B_4 \oplus B_3 \oplus B_2 \oplus P_3\\
    S_2 &= B_4 \oplus B_3 \oplus B_1 \oplus P_2\\
    S_1 &= B_4 \oplus B_2 \oplus B_1 \oplus P_1
\end{align*}

\begin{table}[htbp]
    \centering
    \begin{tabular}{|c|c|c|c|c|c|c|c|c|}
    \hline
        $S_3S_2S_1$ & 000 & 001 & 010 & 011 & 100 & 101 & 110 & 111 \\
        \hline
        错误位 & 无 & $P_1$ & $P_2$ & $B_1$ & $P_3$ & $B_2$ & $B_3$ & $B_4$ \\
        \hline
    \end{tabular}
\end{table}

\section{开关代数与组合逻辑}


\subsection{开关代数}

\subsubsection{开关代数的基本公理}
表 \ref{tab:开关代数的基本公理} 中的5条基本公理完整地定义了开关代数

\begin{table}[htpb]
    \centering
    \caption{开关代数的基本公理}
    \label{tab:开关代数的基本公理}
    \setlength\tabcolsep{1cm}
    \begin{tabular}{ll|c}
        \toprule[1.5pt]
        若 $X\ne 0$ 则 $X=1$  & 若 $X\ne 1$ 则 $X=0$ & {\kaishu 二值性}\\
        \midrule
        若 $X=0$ 则 $X'=1$    & 若 $X=1$ 则 $X'=0$   & {\kaishu 非的真值表}\\
        \midrule
        $0\cdot 0=0$          & $1+1=1$              & \multirow{3}{*}{\shortstack{\kaishu 与的真值表\\\kaishu 或的真值表}}\\
        $1\cdot 1=1$          & $0+0=0$              &\\
        $1\cdot 0=0\cdot 1=0$ & $1+0=0+1=1$          &\\
        \bottomrule
    \end{tabular}
\end{table}


\subsubsection{开关代数的推导方法}

要证明变量比较少的等式，可以采用完备归纳法（穷举法），直接穷举出真值表比较即可\\
要证明 $n$ 个变量的等式，可以采取数学归纳法

其他方式：\\
$A=B \iff A+B'=1$ 且 $A\cdot B'=0$

\paragraph{对偶原理}
对开关代数的任意定理或等式，交换其‘0’‘1’，同时交换其‘$\cdot$’‘$+$’，则结果仍然正确\\
这是因为开关代数的所有基本公理全部都是对偶的

在交换的过程中必须注意保持运算顺序与原先相同
$$
X\cdot Y + X\cdot Z = X\cdot(Y+Z) 
\qquad\Longrightarrow\qquad 
\left\{
\begin{aligned}
    &(X+Y)\cdot (X+Z) = X + (Y\cdot Z) & \text{\color{Green}\unifont ✔️}\\
    & X+Y \cdot  X+Z\ne X + (Y\cdot Z) & \text{\color{red}  \unifont ❌\;\,}
\end{aligned}
\right.
$$

\subsubsection{开关代数的常用定理}
表 \ref{tab:开关代数的单变量定理} 中的定理均可用穷举法证明
\begin{table}[htpb]
    \centering
    \caption{开关代数的单变量定理}
    \label{tab:开关代数的单变量定理}
    \setlength\tabcolsep{1cm}
    \begin{tabular}{ll|l}
        \toprule[1.5pt]
        $X\cdot 1=X$  & $X+0=X$  & {\kaishu 一致性} \\
        $X\cdot 0=0$  & $X+1=1$  & {\kaishu 空元素} \\
        $X\cdot X=X$  & $X+X=X$  & {\kaishu 同一律} \\
        $(X')'=X$     &          & {\kaishu 还原律} \\
        $X\cdot X'=0$ & $X+X'=1$ & {\kaishu 互补律} \\
        \bottomrule[1.5pt]
    \end{tabular}
\end{table}

对于有两个或三个变量的开关代数，见表 \ref{tab:开关代数的二变量和三变量定理}\\
‘与’和‘或’运算都遵循交换律、结合律，在表中省略\\
对于分配律，注意除了可以将逻辑乘分配给逻辑加，还可以把逻辑加分配给逻辑乘（蓝色公式）
\begin{table}[htpb]
    \centering
    \caption{开关代数的二变量和三变量定理}
    \label{tab:开关代数的二变量和三变量定理}
    \setlength\tabcolsep{0.8cm}
    \begin{tabular}{ll|c}
        \toprule[1.5pt]
        $X\cdot Y + X\cdot Z = X\cdot (Y+Z)$ & $\color{blue}(X+Y)\cdot (X+Z) = X+Y\cdot Z$ & {\kaishu 分配律} \\
        $X\cdot (X+Y)=X$     & $X+X\cdot Y=X$  & {\kaishu 吸收} \\
        $(X+Y)\cdot(X+Y')=X$ & $X\cdot Y+X\cdot Y'=X $  & {\kaishu 组合} \\
        \midrule
        \multicolumn{2}{l|}{$X\cdot Y+X'\cdot Z+Y\cdot Z =  X\cdot Y+X'\cdot Z$} & \multirow{2}*{\kaishu 一致性}\\
        \multicolumn{2}{l|}{$(X+Y)\cdot (X'+Z) \cdot (Y+Z) = (X+Y)\cdot (X'+Z)$} & \\
        \bottomrule[1.5pt]
    \end{tabular}
\end{table}


对于最后一条“一致性定理”的说明（由于对偶原理，只需要证明第一条）：\\
若 $Y\cdot Z=1$ 则 $Y=Z=1$，由于 $X$ 与 $X'$ 至少有一个1，最终运算结果必为1\\
若 $Y\cdot Z=0$ 则原式自然成立


$n$ 变量开关代数定理列举如表 \ref{tab:n变量开关代数定理} 所示

\begin{table}[htpb]
    \centering
    \caption{$n$ 变量开关代数定理}
    \label{tab:n变量开关代数定理}
    \setlength\tabcolsep{0.55cm}
    \begin{tabular}{l|c}
        \toprule[1.5pt]
        $(X_1+X_2+\cdots+X_n)' = X_1'\cdot X_2'\cdot \cdots \cdot X_n'$ & \multirow{2}{*}{\kaishu 德摩根定理} \\
        $(X_1\cdot X_2 \cdot \cdots \cdot X_n)' = X_1' + X_2' + \cdots + X_n'$ & \\
        \midrule
        $\big[F(X_1,X_2,\cdots,X_n,\cdot,+)\big]' = F(X_1',X_2',\cdots,X_n',+,\cdot)$ & {\kaishu 广义德摩根定理} \\
        \midrule
        $F(X_1,X_2,\cdots,X_n)=X_1\cdot F(1,X_2,\cdots,X_n)+X'\cdot F(0,X_2,\cdots,X_n)$ &\multirow{2}{*}{\kaishu 香农展开定理}\\
        $F(X_1,X_2,\cdots,X_n)=\big[X_1+F(0,X_2,\cdots,X_n)\big]\cdot \big[X'\cdot F(1,X_2,\cdots,X_n)\big]$ & \\
        \bottomrule[1.5pt]
    \end{tabular}
\end{table}

德摩根定理在逻辑门电路上表现为如图 \ref{fig:德摩根定理在电路上的体现} 所示等价关系
\begin{figure}[htpb]
    \centering
    \begin{circuitikz}
        \draw (0,0) node[nand port] (nand1) {};
        \draw (5,0) node[or port]   (or1)   {};
        \draw (or1.bin 1) node[notcirc,left] {};
        \draw (or1.bin 2) node[notcirc,left] {};
        \node at (2.5,0) {$\Longleftrightarrow$};
        \draw (9,0)  node[nor port] (nor1) {};
        \draw (14,0) node[and port]   (and1)   {};
        \draw (and1.bin 1) node[notcirc,left] {};
        \draw (and1.bin 2) node[notcirc,left] {};
        \node at (11.5,0) {$\Longleftrightarrow$};
    \end{circuitikz}
    \caption{德摩根定理在电路上的体现}
    \label{fig:德摩根定理在电路上的体现}
\end{figure}

\subsection{逻辑函数的标准表示法}

\begin{quote}
    对于如下逻辑函数，它的表达式可写成很多种形式，但互相等价：
    $$
    \begin{aligned}
        F(A,B,C) &= AB+A'C             && {\rm AND-OR} \\
                 &= (A+C)(A'+B)        && {\rm OR-AND} \\
                 &= [(AB)'(A'C)']'     && {\rm NAND-NAND}\\
                 &= [(A+C)'+(A'+B)']'  && {\rm NOR-NOR}\\
                 &= [(A'C')+AB']'      && {\rm AND-OR-NOT}
    \end{aligned}
    $$
\end{quote}

一个逻辑函数的输入输出关系由其真值表完全确定，但若用‘与或非’组成表达式则有很多种\\
可以以真值表为基础构建标准表示法，如表 \ref{tab:用真值表构建逻辑函数的标准表达式} 所示\\
表中 Minterm 列的值只有在同一行的输入下为1，对其他输入为0\\
表中 Maxterm 列的值只有在同一行的输入下为0，对其他输入为1\\
由此可以构建两种标准表达式，分别称标准和式、标准积式，样例见表 \ref{tab:逻辑函数的标准表示法示例}
\begin{enum}
    \item 将所有 $F=1$ 行的 Minterm 相加 得到 $F$
    \item 将所有 $F=0$ 行的 Maxterm 相乘 得到 $F$
\end{enum}

\begin{table}[htpb]
    \centering
    \caption{用真值表构建逻辑函数的标准表达式}
    \label{tab:用真值表构建逻辑函数的标准表达式}
    \includegraphics[width=0.6\textwidth]{figures/用真值表构建逻辑函数的标准表达式.png}
\end{table}

\begin{table}[htpb]
    \centering
    \caption{逻辑函数的标准表示法示例}
    \label{tab:逻辑函数的标准表示法示例}
    \begin{tabular}{cccc|l}
        \toprule[1.5pt]
        $X$ & $Y$ & $Z$ & $F$ & \\
        \hline
        0 & 0 & 0 & 1 & \multirow{8}{*}{
            $\begin{aligned}
                F &= \sum_{XYZ}(0,3,4,6,7)\\
                  &= X'Y'Z'+X'YZ+XY'Z'+XYZ'+XYZ\\
                F &= \prod_{XYZ}(1,2,5)\\
                  &= (X+Y+Z')(X+Y'+Z)(X'+Y+Z')
            \end{aligned}$
        }\\
        0 & 0 & 1 & 0 & \\
        0 & 1 & 0 & 0 & \\
        0 & 1 & 1 & 1 & \\
        1 & 0 & 0 & 1 & \\
        1 & 0 & 1 & 0 & \\
        1 & 1 & 0 & 1 & \\
        1 & 1 & 1 & 1 & \\
        \bottomrule[1.5pt]
    \end{tabular}
\end{table}

将一般逻辑表达式转化为标准形式：\\
若某积式中缺乏一个变量 $Z$ ，则乘以 $Z+Z'$，进而转化为标准形式，例如：
$$
F = X'Y + X'Y'Z = X'Y\cdot (Z+Z') + X'Y'Z = X'YZ+X'YZ'+X'Y'Z
$$

\subsection{组合逻辑表达式化简}
主要依据如下两条定理：
$$
\begin{aligned}
    &(X \cdot Y) + (X \cdot Y') = X \\ 
    &(X + Y) \cdot (X + Y') = X
\end{aligned}
$$

若要使用这两条定理，则需要寻找相邻项\\
相邻项：两个乘积项之间只有一个变量互相取反，例如 $ABC'$ 与 $AB'C'$

特殊化简方式：
\begin{enum}
    \item 若在某表达式中，某项有多个相邻项，则可以对它重复利用，进行多次化简
        $$
        AB'C + ABC + ABC' = (AB'C+ABC) + (ABC+AB'C) = AC + AB
        $$
    \item 按照一定特征排布的$2^i$ 个连续相邻项可以多重化简，从而消去多个变量\\
          下文可以看到，这些项是在卡诺图中矩形分布的
        $$
        \begin{aligned}
        (ABCD + ABCD') + (ABC'D' + ABC'D) = AB\\
        (ABCD + AB'CD) + (AB'CD' + AB'CD) = AD 
        \end{aligned}
        $$
    \item 过分利用第一条规则将产生多余项
        $$
        \begin{aligned}
            AB &= (ABCD + ABCD') + (ABC'D' + ABC'D) \\
               &= (ABCD + ABCD') + {\color{blue}(ABCD'+ABC'D')} + (ABC'D' + ABC'D)\\
               &= ABC + {\color{blue}ABD'} + ABC' \\
               &= AB + {\color{blue}ABD'}
        \end{aligned}
        $$
\end{enum}


通过卡诺图可以简便地寻找相邻项，从而进行化简

\subsubsection{卡诺图}
卡诺图是图形化真值表，2变量卡诺图的形成方式如图 \ref{fig:从真值表中生成卡诺图} 所示\\
3变量、4变量卡诺图的生成方式是类似的

\begin{figure}[htpb]
    \centering
    \input{figures/从真值表中生成2变量卡诺图.tikz.tex}
    \caption{ 从真值表中生成2变量卡诺图 }
    \label{fig:从真值表中生成卡诺图}
\end{figure}

卡诺图的布局特征：
\begin{enum}
    \item n变量的卡诺图有 $2^n$ 个格子
    \item 卡诺图通常最多为4变量，因为二维上的方格最多可以与4个方格相邻
    \item 每个变量将卡诺图分为两部分：原变量、反变量，它们之间存在间隔线
    \item 对于四个方格的行/列，序号的顺序为 0132
    \item 几何上相邻的格子代表了一对相邻项
    \item 上边线与下边线是相连的、左边线与右边线是相连的
\end{enum}

3 变量、4变量卡诺图的布局如图 \ref{fig:三变量、四变量卡诺图布局} 所示

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.9\textwidth]{figures/4变量卡诺图布局图.pdf}
    \caption{三变量、四变量卡诺图布局}
    \label{fig:三变量、四变量卡诺图布局}
\end{figure}

上文总结出的化简经验，可对应到如下行为：
\begin{enum}
    \item 首先，将标准逻辑表达式中出现的乘积项在卡诺图中标示出（标记为1）\\
          图中格子左上角的序号对应标准逻辑表达式中的项序号
    \item 将图中相邻的两个1框出，矩形框将跨越某变量的分界线，这个变量就是被化简掉的变量\\
          剩余变量是否取反取决于矩形框在原参量对应区域还是在反参量对应区域\\
          这样的框既可以是长条形状，也可以是正方形状
    \item 若某矩形区域中全部为1，且总数为 $2^i$ 个，则它们可以化简成一项，消去 $i$ 个变量\\
          矩形框跨越哪些变量的分界线，哪些变量就被化简掉
    \item 一个1可以被多个框所利用，但若某框中的所有1都已经被其他框所包围，此框化简出的项是多余项
\end{enum}

化简过程中应当注意的事项：
\begin{enum}
    \item 每个1都应当至少被一个框所包围，以确保所有项的化简都被考虑到
    \item 优先构造包围 $2^i$ 个1的大矩形框，因为它对应着多重化简，以确保结果最简
\end{enum}

一些概念与技巧
\begin{enum}
    \item 主蕴藏项(prime implicant)：一个内部全1且无法再扩大的矩形框
    \item distinguished 1-cells：只被一个prime implicant所覆盖的1
    \item Essential prime implicant：内含 distinguished 1-cells 的 prime implicant \\
          它是必要的，否则某些 distinguished 1-cells 将不能被包含进来
    \item 对于没有被任何 essential prime implicant 所内含的1，用尽量大的圈将其覆盖
\end{enum}


\subsubsection{卡诺图化简举例}

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.95\textwidth]{figures/卡诺图应用举例1.png}
    \caption{用卡诺图化简逻辑表达式举例1}
    \label{fig:用卡诺图化简逻辑表达式举例1}
\end{figure}

\subsubsection{化简技巧：补项再扣除}

若 $Y$ 是 $X'$ 的子集，也就是说 $X=1$ 时 $Y=0$，则：
\begin{align*}
&X = X \cdot Y' &
&X = (X+Y)\cdot Y'
\end{align*}

若 $m_i,m_j$ 是 $F$ 的真值表中输出为 $0$ 的行，则：
\begin{align*}
    &F = F \cdot m_i' &
    &F = F \cdot (m_i+m_j)'
\end{align*}

进一步，可以先向 $F$ 中补项再扣除：
\begin{align*}
    &F = (F+m_i) \cdot m_i' &
    &F = (F+m_i+m_j) \cdot (m_i+m_j)'
\end{align*}

如果妥善补项，可能会使得卡诺图化简出更加简洁的项，最终有可能使得电路进一步简化

例如 $F=\sum_{ABC}(1,2,5,6)$ 可以表示为图 \ref{fig:卡诺图化简之先补项再扣除} 中所示两种方式\\
左侧方式的化简结果如下，{\kaishu 需要消耗26个MOS管？}
$$
F = A'C+B'C+ABC' = \Big[ (A'C)'\cdot(B'C)' \cdot (ABC')' \Big]'
$$

右侧方式的化简结果，{\kaishu 需要消耗22个MOS管？}
$$
%F = (C+AB)\cdot (ABC)' = C\cdot(ABC)' + AB(ABC)' = \Big[\big[C(ABC)'\big]'\cdot \big[(AB)(ABC)'\big]'\Big]'
F = (C+AB)\cdot (ABC)' = [C'\cdot (AB)']'  \cdot (ABC)'
$$

%$$
%F = (C+AB)\cdot (ABC)' = C\cdot(ABC)' + AB(ABC)' = \Big[\big[C(ABC)'\big]'\cdot \big[(AB)(ABC)'\big]'\Big]'
%$$

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.7\textwidth]{figures/卡诺图化简_先补项再扣除.pdf}
    \caption{卡诺图化简：先补项再扣除}
    \label{fig:卡诺图化简之先补项再扣除}
\end{figure}

\begin{quote}
    对于4输入卡诺图，扣除一项意味着至少是 $\cdot(ABCD)'$\\
    也就是说至少消耗8+4个MOS管，很多时候可能得不偿失
\end{quote}

\subsubsection{含无关输入组的化简}
在某些情况下，系统对某些输入项的输出无关紧要，或是这些输入实际上不会出现\\此时构建电路可以按需决定这些项是0或是1

\begin{quote}
例如对于1位BCD编码，输入项 $\mathtt{1010\sim 1111}$ 不会出现，自然它们的输出也无关紧要
\end{quote}

例如，筛选1位BCD码中的素数（数字1归类为素数），如图 \ref{fig:含无关项的卡诺图化简} 所示，用 d 表示无关项(don't care)\\
若将d都视为0，则电路共需要20个MOS管
$$
F = A'D+A'B'C = \big[(A'D)' \cdot (A'B'C)'\big]'
$$
将右下角的两个d视为1，则电路共需要 16 个MOS管
$$
F = A'D + B'C = \big[(A'D)' \cdot (B'C)'\big]'
$$

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.75\textwidth]{figures/含无关项的卡诺图化简.pdf}
    \caption{含无关项的卡诺图化简}
    \label{fig:含无关项的卡诺图化简}
\end{figure}

\subsubsection{多输出逻辑函数的化简}
某些输出可能共用了同一组输入变量\\
虽然可视为相互独立的两个逻辑函数，但在某些情况下可以共用一些门电路

在输出不太多的情况下，可以手动化简，基本原理是：通过输出之间的与来寻找共有项
\begin{enum}
    \item 对 $n$ 个输出分别绘制卡诺图
    \item 绘制所有 $m$ 项输出的与的卡诺图，其中 $2\le m\le n$，共计$2^n-n-1$ 张卡诺图
    \item 在所有卡诺图中圈出 prime implicant，它们称为 multi-output prime implicant
    \item 其他图上圈出的卡诺圈，若在本图中没有包含0，则应当同步到本图上来（{\kaishu 有可能被本图利用}）
    \item 在 $n$ 张原始输出的卡诺图上，寻找只被1个prime implicant 所覆盖的1 (distinguished 1-cells)\\
          这个essential prime implicant 是必要的
    \item 在 $n$ 张原始输出的卡诺图上，若有还没有被覆盖的1，增减卡诺圈让它们全部被覆盖\\
          注意：在同一位置上的卡诺圈的有无在所有图上是同步的
\end{enum}

以如下两输出函数为例，如图 \ref{fig:多输出卡诺图化简流程}：
\begin{align*}
    &F=\sum_{ABC}(3,6,7) &
    &G=\sum_{ABC}(0,1,3)
\end{align*}

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.95\textwidth]{figures/多输出卡诺图化简.pdf}
    \caption{多输出卡诺图化简流程}
    \label{fig:多输出卡诺图化简流程}
\end{figure}

\begin{enum}
    \item 绘制 $F,G,FG$ 的卡诺图，在每个图上圈出 prime implicant，再同步到其它图上，如图 \ref{fig:多输出卡诺图化简流程} 第一行
    \item 在 $F,G$ 卡诺图中选出distinguished 1-cells（用*标注），则图中 两个竖向的卡诺圈是必要的
    \item 在 $F,G$ 卡诺图中选择适当的卡诺圈包含剩余的1
          如图 \ref{fig:多输出卡诺图化简流程} 第二行，选择小圆圈则需要一个三输入与门，选择两个横向2长度卡诺圈则需要两个两输入与门
\end{enum}

\subsection{时序冒险}

静态冒险：\\
在稳态分析下，输入 IN1 与 IN2 都对应输出 OUT1，但实际电路响应存在延迟\\
将 IN1 切换到 IN2 时，输出可能不会稳定在 OUT1，而是先切换到 OUT2 再回到 OUT1\\
短脉冲 OUT2 称为 glitch，这种现象称为静态时序冒险(Static Timing Hazards)

动态冒险：\\
在稳态分析下，输入 IN1 与 IN2 分别对应输出 OUT1和OUT2，转变前后电路输出改变一次\\
但由于延迟，实际输出可能在 OUT1 和 OUT2 之间震荡，最终稳定在OUT2

一般来说，只有异步时序电路需要排除冒险。其它电路的输出一般只取稳态输出，因而不受冒险影响

\subsubsection{静态冒险}

静态1型冒险(static-1 hazard) 通常由与 - 或电路引起：\\
给定一对输入，它们只有1bit不同，且都产生1的输出\\
在变量发生转变期间，输出可能不维持为1而是可以短暂为0

静态0型冒险(static-0 hazard) 通常由或 - 与电路引起：\\
给定一对输入，它们只有1bit不同，且都产生0的输出\\
在变量发生转变期间，输出可能不维持为0而是可以短暂为1

静态1型冒险举例如图 \ref{fig:静态1型冒险举例} 所示，X与Y维持为1，Z翻转一次\\
若反相器无延迟，则输出应当维持为1\\
考虑反相器延迟，则输出将会有短暂的0
\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.9\textwidth]{figures/static-1_hazard.png}
    \caption{静态1型冒险举例}
    \label{fig:静态1型冒险举例}
\end{figure}

\paragraph{与-或电路消除静态冒险}
两级与-或电路：所有输入连接到几个与门，所有与门的输出连接到或门，或门的输出为最终输出\\
它可与卡诺图建立如下联系：
\begin{enum}
    \item 卡诺圈代表与门，只要输入在圈内则此圈将输出1
    \item 由于或门的存在，只要有一个与门输出1，则整体输出1
    \item 输入有1bit变化，对应着在卡诺图中移动到相邻方格
    \item 若是在某卡诺圈内部移动，则此卡诺圈的输出维持为1，整体输出一定维持为1
    \item 若从卡诺圈A移动到邻接的卡诺圈B，则A: 1$\to$0，B: 0$\to$1，B比A慢就会产生静态1型冒险 
    \item 消除冒险的方式是：增加一个卡诺圈，使得输出维持在此卡诺圈中移动，如图 \ref{fig:与-或电路借助卡诺图消除静态时序冒险}
    \item 若要完全消除冒险，就要在所有卡诺圈之间的邻接部分都增加卡诺圈，如图 \ref{fig:与-或电路完全消除静态时序冒险}
\end{enum}

所增加的卡诺圈实际上是它所连接的卡诺圈的一致项，也就是说，增加一致项将消除冒险\\
在图 \ref{fig:与-或电路借助卡诺图消除静态时序冒险} 中从 $AC'+BC$ 变为 $AC'+BC+AB$

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.75\textwidth]{figures/与-或电路消除静态时序冒险.pdf}
    \caption{与-或电路借助卡诺图消除静态时序冒险}
    \label{fig:与-或电路借助卡诺图消除静态时序冒险}
\end{figure}

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.9\textwidth]{figures/与-或电路完全消除时序冒险.png}
    \caption{与-或电路完全消除静态时序冒险}
    \label{fig:与-或电路完全消除静态时序冒险}
\end{figure}

对于或-与电路也可用类似的方法借助卡诺图消除静态冒险，但卡诺圈应当圈在0上

\subsubsection{动态冒险}

动态冒险只输入改变一次导致输出改变多次后才达到稳态\\
若有多个具有不同延迟的通路，可能会导致动态冒险

例如图 \ref{fig:动态冒险举例} 中两个不同延迟的或门造成动态冒险\\
其中一个或门很慢（用蓝色正体代表它造成的改变），另一个或门更慢（用蓝色斜体代表它造成的改变）\\
其它元件的延迟忽略不计
    
\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.95\textwidth]{figures/动态冒险示意图.png}
    \caption{动态冒险举例}
    \label{fig:动态冒险举例}
\end{figure}


\section{数字设计实践}

\subsection{文档标准}

\subsubsection{信号名与有效电平}

对于控制信号，通常用其控制的功能来命名。依据有效电平追加后缀：\\
Active High: 信号为1时，信号名所对应的功能被激活，不再追加后缀\\
Active Low:  信号为0时，信号名所对应的功能被激活，通常在信号名末追加 {\ttfamily \_L}

\begin{quote}
    对于数据信号、地址信号等通常直接命名如 {\upshape\ttfamily DATA[7:1],ADDR[31:0]}\\
    也用后缀 {\upshape\ttfamily \_L} 表示被取反的信号
\end{quote}

约定：信号在模块内部都是 Active High\\
在信号线上若为 Active Low 则在模块引脚处加反相圈，如图 \ref{fig:在引脚处加反相圈以维持模块内部高电平有效} 所示

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.4\textwidth]{figures/在引脚处加反向圈以维持模块内部高电平有效.png}
    \caption{在引脚处加反相圈以维持模块内部高电平有效}
    \label{fig:在引脚处加反相圈以维持模块内部高电平有效}
\end{figure}

\begin{quote}
    图 \ref{fig:在引脚处加反相圈以维持模块内部高电平有效} 中向下的小三角为接地，水平短横线为电源电压
\end{quote}

为使逻辑电路图尽量易读，通常确保信号仅在某些导线段上是低电平有效，也就是：
\begin{enum}
    \item 若输入输出信号是低电平有效，则将反相圈直接暴露在输入输出端口
    \item 若某段导线上信号是低电平有效，则确保该导线的端口都连接反相圈，而不是直接通入元器件中
\end{enum}

如图 \ref{fig:“圈到圈”电路图绘制原则} 中 a,b 电路图等价，但b图通过将低电平有效信号限制在导线上，更易读

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.9\textwidth]{figures/圈到圈逻辑电路图.png}
    \caption{“圈到圈”电路图绘制原则}
    \label{fig:“圈到圈”电路图绘制原则}
\end{figure}

\subsubsection{原理图绘制原则}
为清晰起见，只允许 {\sffamily T} 字形导线连接，而十字交叉相连的导线全部改成两个 {\sffamily T} 字形\\
电路图中的十字交叉项一律视为跃过而不相连，如图 \ref{fig:电路图绘制规则} 所示

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.6\textwidth]{figures/电路图绘制规则.png}
    \caption{原理图绘制规则}
    \label{fig:电路图绘制规则}
\end{figure}

对于比较大的原理图，通常采取如下两种绘制结构：
\begin{enum}
\item 平面结构：如图 \ref{fig:平面原理图结构}，将一大张平面图分割到各张纸上，导线可以直接连接到临近纸张，也可通过标号连接到其它纸张
\item 分层结构：如图 \ref{fig:分层原理图结构}，将大型元件封装成方框，其内部结构绘制在其它纸张上
\end{enum}

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.9\textwidth]{figures/平面原理图结构.png}
    \caption{平面原理图结构}
    \label{fig:平面原理图结构}
\end{figure}

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.9\textwidth]{figures/分层原理图结构.png}
    \caption{分层原理图结构}
    \label{fig:分层原理图结构}
\end{figure}

\subsubsection{总线}
用粗线表示一捆具有相同功能的线，如图 \ref{fig:原理图总线示意图} 所示\\
用方括号表示总线名的范围，以及总线宽度

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.8\textwidth]{figures/原理图总线示意图.png}
    \caption{原理图总线示意图}
    \label{fig:原理图总线示意图}
\end{figure}

\begin{quote}
    一些中英文名词对照：
    \begin{center}
        \upshape
        \begin{tabular}{cc|cc|cc}
            \toprule
            中文 & English & 中文 & English & 中文 & English\\ 
             \midrule
            总线 & BUS     & 原理图 & Schematic & 布局 & Layout\\
            有效电平 &Active level & 低电平有效 &Active Low & 高电平有效 &Active High\\
             \bottomrule
        \end{tabular}
    \end{center}
\end{quote}
\subsection{电路时序}

\subsubsection{时序图}

绘制时序图的一些要点如下，举例如图 \ref{fig:时序图举例} 所示
\begin{enum}
    \item 电平的转化过程用斜线绘制，以示需要消耗时间。用斜线中点对应时间表示转化发生的时间点
    \item 转化时间、上升时间、下降时间
    \item 用箭头表示输入输出的因果性
    \item 时序图上可以看出不同通路具有不同的延迟
    \item 延迟可能不是确定的，而具有一定的随机性，可在时序图中用一组平行斜线表示
\end{enum}

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.65\textwidth]{figures/时序图举例.png}
    \caption{时序图举例}
    \label{fig:时序图举例}
\end{figure}

有时不关心电平高低，只关心其翻转，则可以按照图 \ref{fig:只关心电平翻转的时序图} 所示绘制
\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.6\textwidth]{figures/时序图举例2.png}
    \caption{只关心电平翻转的时序图}
    \label{fig:只关心电平翻转的时序图}
\end{figure}

对于总是按照相同时序工作的一组总线，可以合并绘制\\
有时可以直接标注十六进制数字来表现各线在此刻的电平高低，如图 \ref{fig:总线合并绘制并标注值的时序图} 所示

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.6\textwidth]{figures/时序图举例3.png}
    \caption{总线合并绘制并标值的时序图}
    \label{fig:总线合并绘制并标注值的时序图}
\end{figure}

\subsubsection{传输延迟的影响因素}
传输延迟(propagation delay)：通路输入端变化引起输出端变化所需要的时间\\
通常受到如下因素影响：
\begin{enum}
    \item 温度、电源电压（通常电压低电路慢）
    \item 输入的转换时间：输入翻转慢则输出翻转慢
    \item 输出端负载：输出端所连接的元件的电气特性可能会阻碍输出端电平变化
    \item 翻转方向：电平从低到高、从高到低两种情况耗时可能不同
    \item 光速延迟：大约 $5\;\rm ns/m$，对高频芯片影响大
    \item 噪声与串扰：电气噪声（包括临近线路正在发生的翻转过程）使得输入到达开关阈值的时间有随机量
    \item 元件制造公差
\end{enum}

通常依据 IC 制造厂家所说明的 “最大”“典型”以及 “最小”传输延迟来做出工程估算
\begin{enum}
    \item 最大延迟：在给定条件下的最大延迟。若条件恶化则延迟仍有可能进一步增大
    \item 典型延迟：状况良好的元件在比较理想的条件下工作时的延迟
    \item 最小延迟：在部分高速器件中指定最小延迟以满足锁存器、触发器等元件的时序要求
\end{enum}

一些器件的输出端，由高变低的延迟 $t_{\rm pHL}$ 与由低变高的延迟 $t_{\rm pLH}$ 可能是不同的，需分别标注\\
对于CMOS器件，$t_{\rm pLH} \approx t_{\rm pHL}$，有时只标注 $t_{\rm pd}$

\subsection{基于HDL的数字设计}
\subsubsection{HDL设计工具组}

硬件描述语言HDL: Hardware Describe Language

HDL工具组通常主要由如下工具组成：
\begin{enum}
    \item 编译器(compiler)：HDL 文件转化为 RTL 文件（寄存器传输语言）
    \item 综合器(synthesizer)：依据给定的硬件平台，将RTL转化为实际电路\\
         （选取实现RTL的可用元件、元件布局、连线）
    \item 模拟器(simulator)：给定输入信号，模拟HDL模型在一定时间内各个信号的值以及输出
\end{enum}

其它辅助工具：
\begin{enum}
    \item 原理图展示器(schematic viewer)：依据HDL编译出来的RTL生成HDL模型的原理图
    \item 芯片展示器(chip viewer)：查看综合器最终实现的布线
    \item 约束编辑器(constraints editor)：更改综合器等工具的决策依据，例如提高某些重要需求的优先权
    \item 时序分析器(timing analyzer)：计算信号通路的延迟时间，计算最差通路及其延迟
    \item 后插注解器(back annotator)：将计算出的延迟包含到原始HDL文件中，以便在仿真中考虑延迟
\end{enum}

\subsubsection{HDL设计流程}

如图 \ref{fig:HDL设计流程示意图} 所示
\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.7\textwidth]{figures/HDL设计流程示意图.pdf}
    \caption{HDL设计流程示意图}
    \label{fig:HDL设计流程示意图}
\end{figure}

\subsection{一些概念}

\subsubsection{迭代电路Iterative circuit}

迭代电路是特殊类型的组合电路，由 $n$ 个相同的模块组成，如图 \ref{fig:迭代电路基本结构} 所示\\
每个模块包括：主输入、主输出、级联输入、级联输出\\
迭代电路的两端的级联输入/输出分别称为：边界输入、边界输出

迭代电路通常用于执行迭代算法（循环）\\
例如：迭代比较器、串行进位加法器

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.95\textwidth]{figures/迭代电路基本结构.png}
    \caption{迭代电路基本结构}
    \label{fig:迭代电路基本结构}
\end{figure}


\section{组合逻辑元件}

\subsection{可编程逻辑设备PLD}
\subsubsection{可编程逻辑阵列PLA}

PLA：两级\texttt{AND-OR}器件，在器件规模允许的范围内，可实现任何“积之和”逻辑表达式\\
PLA内部结构如图 \ref{fig:PLA结构示意图} 所示，也可简化绘制如图 \ref{fig:PLA结构简化示意图} 所示，主要特征如下：
\begin{enum}
    \item n个输入，m个输出(\texttt{OR})，p个乘积项(\texttt{AND})
    \item 蓝色 $\color{blue}\times$ 部分称为 fuse，可编程控制其通断，可用浮栅元件制造断电非易失的fuse
    \item 在 \texttt{AND} 阵列中需要 $2np$ 个fuse，在 \texttt{OR}阵列中需要 $mp$ 个fuse
    \item $n$ 个输入都直接连接到缓冲器，产生原变量及其反变量
    \item $p$ 个与门按需连接到一些变量或其反变量上，生成 $p$ 个乘积项（{\kaishu 卡诺圈}） 
    \item $m$ 个或门按需连接到一些乘积项上，生成 $m$ 个输出 
    \item 在 $n$ 输入$m$输出卡诺图上，若所需要的卡诺圈数量大于 $p$ 则无法用此PLA实现
\end{enum}

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.84\textwidth]{figures/PLA结构示意图.png}
    \caption{PLA结构示意图}
    \label{fig:PLA结构示意图}
\end{figure}

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.55\textwidth]{figures/PLA结构简化示意图.png}
    \caption{PLA结构简化示意图}
    \label{fig:PLA结构简化示意图}
\end{figure}

事实上对于CMOS型PLD而言，图 \ref{fig:PLA结构简化示意图} 所示简化结构才更接近实际：\\
一根导线上连接1个上拉电阻，多个下拉MOS开关，从而实现 \texttt{NAND} 逻辑\\
在电路上调换原参量与反参量的位置即可得到多输入 \texttt{AND}，类似可构建多输入 \texttt{OR} 

\begin{quote}
    对于 $n$ 输入 \texttt{AND-OR} 逻辑，异或（奇偶校验）是最消耗乘积项的，需要 $2^{n-1}$ 个乘积项
\end{quote}


\subsubsection{可编程阵列逻辑 PAL}
PAL是特殊的PLA，其\texttt{OR}阵列是固定连接的，典型的基本结构如图 \ref{fig:PAL结构示意图} 所示 
\begin{enum}
    \item 或门的输出被反相后才最终输出
    \item 每个或门与7个与门连接，构成正常的 \texttt{AND} 阵列\\
          另有1个与门可控制反相器的通断，也就控制了本输出是否有效
    \item 每个输出最多可以使用7个乘积项（{\kaishu  卡诺圈}）
    \item 每个输出都是相互独立的，而不能共用乘积项
    \item 有些引脚可以是输入，也可以是输出。若妥善编程可作\texttt{IO} 双向引脚
    \item 这些\texttt{IO}引脚可以在一定程度上实现反馈
\end{enum}

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.9\textwidth]{figures/PAL结构示意图.png}
    \caption{PAL结构示意图}
    \label{fig:PAL结构示意图}
\end{figure}

\subsection{译码器Decoder}
二进制译码器有如下特征：
\begin{enum}
    \item $n$ 输入，$m$ 输出，其中 $m$ 位输出中有且只有一位是 $1$
    \item 输入有 $2^n$ 种，输出有 $m$ 种，因此 $m\le 2^n$
    \item 部分译码器含有一个或多个 ENABLE 输入，若 ENABLE 无效则输出全0或其它无效输出
\end{enum}

\begin{quote}
    译码器的输入编码字通常称为\textbf{地址位}\upshape (address bit)
\end{quote}

3-8译码器的真值表与逻辑符号如表 \ref{tab:74x138型3选8译码器真值表} 和图 \ref{fig:74x138型3选8译码器电路符号} 所示
（{\kaishu 以\texttt{74x138}型3-8译码器为例}）\\
注意 \texttt{C,B,A} 的高低位关系
\begin{table}[htpb]
    \centering
    \caption{3-8译码器真值表}
    \label{tab:74x138型3选8译码器真值表}
    \includegraphics[width=0.9\textwidth]{figures/3选8译码器真值表.png}
\end{table}

\begin{figure}[htpb]
    \centering
    \qquad
    \includegraphics[width=0.32\textwidth]{figures/74x138型3选8译码器示意图.png}
    \qquad
    \begin{tikzpicture}
        \draw[thick] (0,0) rectangle (1.7,3.9);
        \draw (-0.7,0.65) node[left] {$A$} -- (0,0.65);
        \draw (-0.7,1.95) node[left] {$B$} -- (0,1.95);
        \draw (-0.7,3.25) node[left] {$C$} -- (0,3.25);
        \draw (0.5,0.433*1) node[anchor=west] {\small $A\;B\;C\;$};
        \draw (0.5,0.433*2) node[anchor=west] {\small $A\;B\;C'$};
        \draw (0.5,0.433*3) node[anchor=west] {\small $A\;B'C\;$};
        \draw (0.5,0.433*4) node[anchor=west] {\small $A\;B'C'$};
        \draw (0.5,0.433*5) node[anchor=west] {\small $A'B\;C\;$};
        \draw (0.5,0.433*6) node[anchor=west] {\small $A'B\;C'$};
        \draw (0.5,0.433*7) node[anchor=west] {\small $A'B'C\;$};
        \draw (0.5,0.433*8) node[anchor=west] {\small $A'B'C'$};
        \foreach \i in {1,2,...,8}
        {
            \draw (2.08-0.3,0.433*\i) circle[radius=0.08];
            \draw (2.16-0.3,0.433*\i) -- (2.3,0.433*\i);
        }
    \end{tikzpicture}
    \caption{74x138型3选8译码器逻辑电路符号、输入输出关系}
    \label{fig:74x138型3选8译码器电路符号}
\end{figure}

译码器的每个输出端口实际上是一个乘积项，通过或门组合所需要的乘积项就可以实现逻辑表达式\\
译码器的输出也经常作为片选信号

大型译码器通常很难直接构建，而是通过小型译码器组合得到，有级联、预译码两种方式

\subsubsection{大型译码器：级联(cascading)}
如图 \ref{fig:大型译码器：级联法} ，高地址位 \texttt{N[4:3]} 用于一级译码器选择二级译码器，
低地址位 \texttt{N[2:0]} 用于二级译码器译码\\
如果第一级译码只有一位，可以省略第一级译码器，直接将此位通入第二级的 \texttt{ENABLE}、\texttt{ENABLE\_L}

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.77\textwidth]{figures/大型译码器_级联法.png}
    \caption{大型译码器：级联法}
    \label{fig:大型译码器：级联法}
\end{figure}

输入每增加1位，二级译码器数量翻倍

\subsubsection{大型译码器：预译码(predecoding)}
更大型的译码器通常采用预译码的方法构建

采用预译码的6-64二进制译码器结构如图 \ref{fig:大型译码器：预译码法} 所示

以输出 \texttt{Y1} 为例，若译码结果为 \texttt{Y1}则说明：
\begin{enum}
    \item \texttt{ENABLE=1}
    \item \texttt{A[5:4]=00 \&\& A[3:2]=00 \&\& A[1:0]=01}
    \item 上一条等价于：$\mathtt{A_5'A_4'}$ \;\texttt{\&\&}\; $\mathtt{A_3'A_2'}$ \;\texttt{\&\&}\; $\mathtt{A_1'A_0}$，
          这分别对应于三个预译码器的输出，相与即得结果
    \item \texttt{ENABLE}信号只需接一个预译码器\\
          当\texttt{ENABLE=0} 时此预译码器的4个输出全为\texttt{0}，经过 \texttt{AND} 后所有输出为 \texttt{0}
\end{enum}

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.54\textwidth]{figures/大型译码器_预译码.png}
    \caption{大型译码器：预译码法}
    \label{fig:大型译码器：预译码法}
\end{figure}

若图 \ref{fig:大型译码器：预译码法} 中改用2个3-8译码器，则： 
\begin{enum}
    \item 预译码器变复杂
    \item 垂直导线由12根变为16根
    \item 输出端的与门由3输入变为2输入
    \item 预译码器的每个输出端需要驱动的输入端口数：由16变为8
    \item 综合起来看，电路规模变小
\end{enum}

\subsubsection{7段显示译码器}
用7段LED管显示数字$0\sim 9$，如图 \ref{fig:七段译码器示意图} 所示，具有7个输出引脚 $\mathtt{a\sim g}$

实际上共有 $2^7$ 种输出组合，但一般只取与数字$0\sim9$外观相似的输出，共计10种\\
因此输入控制用4 位 BCD 码，\emph{输入引脚有4个}\\
有时还显示其它几个符号，凑齐16种输出 

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.95\textwidth]{figures/七段译码器.png}
    \caption{七段译码器示意图}
    \label{fig:七段译码器示意图}
\end{figure}

\subsection{优先级编码器priority encoder}
几个元件都有权请求使用某资源，但此资源在同一时间只能被一个元件使用\\
为防止在同一时间有多个请求，引入优先级(priority)\\
则可以通过优先级编码器来决定运行模式

优先级编码器逻辑电路符号如图 \ref{fig:优先级编码器、可级联优先级编码器} 所示
\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.5\textwidth]{figures/优先级编码器.png}
    \caption{优先级编码器、可级联优先级编码器}
    \label{fig:优先级编码器、可级联优先级编码器}
\end{figure}

对于一般的优先级编码器（不可级联），其输入输出关系为：
$$
\begin{aligned}
    H_7 &= I_7\\
    H_6 &= I_6 \cdot I_7' \\
    H_5 &= I_5 \cdot I_6' \cdot I_7' \\
        &\cdots \\
    H_0 &= I_0 \cdot I_1' \cdot I_2'\cdot I_3'\cdot I_4'\cdot I_5'\cdot I_6'\cdot I_7'
\end{aligned}
\qquad\Longrightarrow\qquad 
\begin{aligned}
    A_2 = H_4 + H_5 + H_6 + H_7\\
    A_1 = H_2 + H_3 + H_6 + H_7\\
    A_0 = H_1 + H_3 + H_5 + H_7\\
\end{aligned}
$$

当选取到 $I_x$ 时输出 3 位二进制数 $x$，当所有输入均为 $0$ 时输出也为 $0$\\
\texttt{IDLE} 引脚仅在输入均为 0 的情况下输出1，否则输出0

对于可级联型优先级编码器，其真值表如表 \ref{tab:可级联型优先级编码器真值表} 所示 \\
\texttt{GS} 引脚可记为Got Something，表示 \texttt{ENABLE=1} 且收到了请求，也即本编码器输出有效\\
\texttt{EO} 引脚表示本元件 \texttt{ENABLE=1} 但没有收到请求，用来级联
\begin{table}[htpb]
    \centering
    \caption{可级联型优先级编码器真值表}
    \label{tab:可级联型优先级编码器真值表}
    \includegraphics[width=0.72\textwidth]{figures/可级联型优先级编码器真值表.png}
\end{table}

通过级联制造大型优先级编码器的原理如下：
\begin{enum}
    \item 上级编码器处理高优先级请求，下级编码器处理低优先级请求
    \item 上级 \texttt{ENABLE=0} 则下级 \texttt{ENABLE=0} 
    \item 上级 \texttt{ENABLE=1} 且收到至少一个请求，则下级 \texttt{ENABLE=0}
    \item 上级 \texttt{ENABLE=1} 且没有收到任何请求，则下级 \texttt{ENABLE=1}
\end{enum}

此操作通过将上一级的 \texttt{EO} 引脚连接到下一级的 \texttt{EI} 引脚来实现，如图 \ref{fig:优先级编码器的级联}\\
输出细节如下：
\begin{enum}
    \item \texttt{RA4} 将一组32个分解为两组16个\\
          \texttt{RA4=1} 对应于 $16\sim31$，由1级、2级的 \texttt{GS} 或运算得到
    \item \texttt{RA3} 将 两组16个分解为4组8个\\
          \texttt{RA3=1} 对应于 $8\sim 16,\;24\sim31$，由1级、3级的 \texttt{GS} 或运算得到 
    \item 其它3位输出直接与4个编码器的3位输出
    \item 只要有1个编码器 \texttt{GS=1} 则整体上32位编码器 \texttt{RGS=1} 
\end{enum}

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.8\textwidth]{figures/优先级编码器的级联.png}
    \caption{优先级编码器的级联}
    \label{fig:优先级编码器的级联}
\end{figure}

\subsection{多路复用器multiplexer}
选择几个输入数据中的一个作为输出数据\\
可用译码器 + 可控开关组成多路复用器，如图 \ref{fig:多路复用器原理图}

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.45\textwidth]{figures/多路复用器原理图.png}
    \includegraphics[width=0.30\textwidth]{figures/多路复用器原理图0.png}
    \caption{多路复用器原理图}
    \label{fig:多路复用器原理图}
\end{figure}

若数据从左向右传输，称为多路复用器 (MUX) \\
若数据从右向左传输，称为多路分配器 (DMUX)\\
两者的逻辑电路符号如图 \ref{fig:MUX和DMUX逻辑电路符号} 所示 

\begin{figure}[H]
    \centering
    \includegraphics[width=0.55\textwidth]{figures/MUX和DMUX逻辑电路符号.png}
    \caption{MUX和DMUX逻辑电路符号}
    \label{fig:MUX和DMUX逻辑电路符号}
\end{figure}

若希望数据能双向传输，则图 \ref{fig:多路复用器原理图} 中可控开关是 CMOS 传输门\\
若只需要数据单向传输，则图 \ref{fig:多路复用器原理图} 中可控开关用与门（{\kaishu 与门无高阻态，输出必须用或门整合}）

对于用与门作可控开关的MUX，译码器电路可与可控开关与门相合并\\
如图 \ref{fig:4输入1位宽MUX逻辑电路图} 为4输入1位宽MUX
\begin{enum}
\item 需要 $\log_2(4/1)=2$ 个控制信号 
\item 每个与门接受的输入有：1位 \texttt{DATAx}，2位控制信号，1位 \texttt{ENABLE} 
\item 输入的 4 个 \texttt{DATAx} 中有且只有 1 个能通过与门 
\item 最终用或门整合3路无效信号、1路有效信号得到1路输出信号
\end{enum}

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.6\textwidth]{figures/4输入1输出MUX逻辑电路图.png}
    \caption{4输入1位宽MUX逻辑电路图，需要2个控制信号}
    \label{fig:4输入1位宽MUX逻辑电路图}
\end{figure}

\begin{quote}
    对于8输入1输出MUX则需要：\\
    8个5输入与门 (\texttt{ENABLE, DATAx, CTRL$\times$}3)\\
    1个8输入或门
\end{quote}

MUX的输入输出也可以是等宽度的总线，
只需要将多个小位宽MUX并联使用即可

\subsubsection{MUX的扩展}
用4个8输入1位宽MUX组合成32输入1位宽MUX，如图 \ref{fig:小型MUX组合成大型MUX} 所示
\begin{enum}
    \item 控制信号高2位：通过译码器片选4个MUX中的一个
    \item 控制信号低3位：控制4个MUX分别进行8选1 
    \item 4个MUX的输出有且仅有1个有效，通过4输入或门得到输出信号
\end{enum}

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.9\textwidth]{figures/大型多路复用器.png}
    \caption{具有更多输入的MUX}
    \label{fig:小型MUX组合成大型MUX}
\end{figure}

\subsubsection{用MUX实现逻辑表达式}
将MUX视为译码器+可控开关，则可得到MUX的逻辑表达式（{\kaishu 不考虑\texttt{ENABLE}}）
$$
Y = \sum_{\mathtt{SEL}_i} m_i \cdot D_i
$$

通过控制 $D_i$ 就可以用多路复用器直接实现逻辑表达式，例如：
\begin{align*}
    F &= \sum_{ABC} (1,2,6,7)\\
      &= 0m_0 + 1m_1 + 1m_2 + 0m_3 + 0m_4 + 0m_5 + 1m_6 + 1m_7 
\end{align*}

$D_i$ 也不必非0即1，也可输入一个变量，通常是最低位，如表 \ref{tab:用MUX实现逻辑表达式：真值表分区} 所示\\
也可利用两个多路复用器，用最高位作片选信号，用最低位作输入信号，其它位作 \texttt{SEL} 信号，
同样用表 \ref{tab:用MUX实现逻辑表达式：真值表分区}

\begin{table}[htpb]
    \centering
    \caption{用MUX实现逻辑表达式：真值表分区}
    \label{tab:用MUX实现逻辑表达式：真值表分区}
    \begin{tabular}{cc|ccl|c}
        \toprule
        $A$ & $B$ & $C$ & $F$ & $F$ 与 $C$ & 逻辑表达式\\
        \midrule
        0 & 0 & 0 & 0  &\multirow{2}{*}{$F=C$} &\multirow{8}{*}{ %
            $\begin{aligned}
                F &= \sum_{ABC} (1,2,6,7) \\
                  &= A'B'C + A'BC'+ABC'+ ABC\\
                  &= (A'B'){\color{blue}C} + (A'B){\color{blue}C'} + (AB'){\color{blue}0} + (AB){\color{blue}1}
            \end{aligned}$
        }\\
        0 & 0 & 1 & 1  &                       &\\
        \cline{1-5}
        0 & 1 & 0 & 1  &\multirow{2}{*}{$F=C'$}&\\
        0 & 1 & 1 & 0  &                       &\\
        \cline{1-5}
        1 & 0 & 0 & 0  &\multirow{2}{*}{$F=0$} &\\
        1 & 0 & 1 & 0  &                       &\\
        \cline{1-5}
        1 & 1 & 0 & 1  &\multirow{2}{*}{$F=1$} &\\
        1 & 1 & 1 & 1  &                       &\\
        \bottomrule
    \end{tabular}
\end{table}

上述三种方式的在逻辑电路中分别表现为图 \ref{fig:用多路复用器实现逻辑表达式举例} 中所示三种接法

\begin{figure}[htpb]
    \centering
    \begin{tikzpicture}
        \draw[thick] (0,0) rectangle (1.6,4.4);
        \draw (-0.5, 0.2+0.4*0 ) node[left]{1}   -- ++(0.5,0) node[right] {\texttt{D7}};
        \draw (-0.5, 0.2+0.4*1 ) node[left]{1}   -- ++(0.5,0) node[right] {\texttt{D6}};
        \draw (-0.5, 0.2+0.4*2 ) node[left]{0}   -- ++(0.5,0) node[right] {\texttt{D5}};
        \draw (-0.5, 0.2+0.4*3 ) node[left]{0}   -- ++(0.5,0) node[right] {\texttt{D4}};
        \draw (-0.5, 0.2+0.4*4 ) node[left]{0}   -- ++(0.5,0) node[right] {\texttt{D3}};
        \draw (-0.5, 0.2+0.4*5 ) node[left]{1}   -- ++(0.5,0) node[right] {\texttt{D2}};
        \draw (-0.5, 0.2+0.4*6 ) node[left]{1}   -- ++(0.5,0) node[right] {\texttt{D1}};
        \draw (-0.5, 0.2+0.4*7 ) node[left]{0}   -- ++(0.5,0) node[right] {\texttt{D0}};
        \draw (-1.0, 0.2+0.4*8 ) node[left]{$A$} -- ++(1.0,0) node[right] {\texttt{SEL2}};
        \draw (-1.0, 0.2+0.4*9 ) node[left]{$B$} -- ++(1.0,0) node[right] {\texttt{SEL1}};
        \draw (-1.0, 0.2+0.4*10) node[left]{$C$} -- ++(1.0,0) node[right] {\texttt{SEL0}};
        \draw (1.6,2.2) node[left]{\texttt Y} -- ++(0.5,0) node[right]{$F$};
    \end{tikzpicture}\qquad
    \begin{tikzpicture}
        \draw[thick] (0,0) rectangle (1.6,4.4);
        \draw (-0.5, 0.3+0.7*0 ) node[left]{1\;\,} -- ++(0.5,0) node[right] {\texttt{D0}};
        \draw (-0.5, 0.3+0.7*1 ) node[left]{0\;\,} -- ++(0.5,0) node[right] {\texttt{D1}};
        \draw (-0.5, 0.3+0.7*2 ) node[left]{$C' $} -- ++(0.5,0) node[right] {\texttt{D2}};
        \draw (-0.5, 0.3+0.7*3 ) node[left]{$C\;$} -- ++(0.5,0) node[right] {\texttt{D3}};
        \draw (-1.0, 0.6+0.7*4 ) node[left]{$A$}   -- ++(1.0,0) node[right] {\texttt{SEL1}};
        \draw (-1.0, 0.6+0.7*5 ) node[left]{$B$}   -- ++(1.0,0) node[right] {\texttt{SEL0}};
        \draw (1.6,2.2) node[left]{\texttt Y} -- ++(0.5,0) node[right]{$F$};
    \end{tikzpicture}\qquad
    \begin{tikzpicture}
        \draw[thick] (0,0) rectangle (1.6,4.4);
        \draw (-0.5, 0.3+0.6*0 ) node[left]{1\;\,} -- ++(0.5,0) node[right] {\texttt{2D1}};
        \draw (-0.5, 0.3+0.6*1 ) node[left]{0\;\,} -- ++(0.5,0) node[right] {\texttt{2D0}};
        \draw (-0.5, 0.3+0.6*2 ) node[left]{$A\;$} -- ++(0.5,0) node[right] {\texttt{2EN}};
        \draw (-0.5, 0.3+0.6*3 ) node[left]{$C' $} -- ++(0.5,0) node[right] {\texttt{1D1}};
        \draw (-0.5, 0.3+0.6*4 ) node[left]{$C\;$} -- ++(0.5,0) node[right] {\texttt{1D0}};
        \draw (-0.5, 0.3+0.6*5 ) node[left]{$A' $} -- ++(0.5,0) node[right] {\texttt{1EN}};
        \draw (-1.0, 0.5+0.6*6 ) node[left]{$B$}   -- ++(1.0,0) node[right] {\texttt{SEL}};
        \draw (1.6,1.5) node[left]{\texttt{2Y}} -- ++(0.5,0) -- ++(0,+0.4);
        \draw (1.6,2.9) node[left]{\texttt{1Y}} -- ++(0.5,0) -- ++(0,-0.4);
        \draw (2.1,2.2) node{\texttt{OR}} circle[radius=0.3];
        \draw (2.4,2.2) -- ++(0.5,0) node[right] {$F$};
    \end{tikzpicture}
    \caption{用多路复用器实现逻辑表达式举例}
    \label{fig:用多路复用器实现逻辑表达式举例}
\end{figure}


\subsection{三态器件}
输出除了0,1之外还可能是高阻态 z，也即输出引脚悬空，电路断路\\
如图 \ref{fig:三态缓冲器/反相器示意图} 为缓冲器/反相器的三态器件，顶部 \texttt{ENABLE} 输入有效时元件正常工作，否则为高阻态

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.35\textwidth]{figures/三态器件.png}
    \caption{三态缓冲器/反相器示意图}
    \label{fig:三态缓冲器/反相器示意图}
\end{figure}

通常，三态器件进入高阻态速度 > 脱离高阻态速度\\
因此可用来实现MUX，如图 \ref{fig:三态器件作可控开关实现MUX} 所示

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.7\textwidth]{figures/三态器件作可控开关实现MUX.png}
    \caption{三态器件作可控开关实现MUX}
    \label{fig:三态器件作可控开关实现MUX}
\end{figure}

用一组三态缓冲器制造总线开关，如图 \ref{fig:三态缓冲器74x541} 所示
\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.7\textwidth]{figures/三态缓冲器74x541.png}
    \caption{三态缓冲器74x541：总线开关}
    \label{fig:三态缓冲器74x541}
\end{figure}

\subsection{异或门与奇偶校验电路}
异或运算：奇数个1输出1，偶数个1输出0
$$
X \oplus Y = X'\cdot Y + X\cdot Y'
$$

%异或运算的几项作用：
%\begin{enum}
%    \item 比较：多个异或门实现多位数字比较
%    \item 奇偶校验
%    \item 加法
%    \item 计数
%\end{enum}

\subsubsection{异或电路}
如图 \ref{fig:三种异或电路} 为异或电路的多种实现方式，通常采用 CMOS 传输门构成的多路复用器来实现异或

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.6\textwidth]{figures/三种异或电路.png}
    \caption{三种异或电路}
    \label{fig:三种异或电路}
\end{figure}

对异或门三个引脚中的任意两个取反，结果仍然满足异或逻辑，如图 \ref{fig:等效的异或门} 所示

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.7\textwidth]{figures/等效的异或门.png}
    \caption{等效的异或门}
    \label{fig:等效的异或门}
\end{figure}

\subsubsection{奇偶校验电路}
通过异或门的级联就可以得到奇校验电路，如图 \ref{fig:奇校验电路}\\
有链状、树状两种级联方式，有时也组合使用（树状更快）

\emph{注意}：奇校验电路在输入奇数个1时输出1

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.68\textwidth]{figures/奇偶校验电路.png}
    \caption{两种奇校验电路：链状、树状}
    \label{fig:奇校验电路}
\end{figure}

在奇校验电路的任意位置加一个反相器，得到偶校验电路\\
奇校验电路用来产生偶校验位，偶检验电路用来产生奇校验位

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.83\textwidth]{figures/奇偶校验模块74x280.png}
    \caption{组合使用链状、树状奇偶校验电路}
    \label{fig:奇偶校验模块74x280}
\end{figure}

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.83\textwidth]{figures/奇偶校验用于储存器.png}
    \caption{奇偶校验用于储存器}
    \label{fig:奇偶校验用于储存器}
\end{figure}

\subsubsection{奇偶校验电路的应用}

对储存器实现奇偶校验，如图 \ref{fig:奇偶校验用于储存器} 所示\\
实现7bit汉明码纠错电路，如图 \ref{fig:汉明码7bit纠错电路} 所示（4bit数据位，3bit检错位）

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.8\textwidth]{figures/汉明码7bit纠错电路.png}
    \caption{汉明码7bit纠错电路}
    \label{fig:汉明码7bit纠错电路}
\end{figure}

\subsection{比较器comparator}
若只需要比较机器数是否相等，称为比较器\\
若还需要比较机器数大小关系，称为数值比较器\\
有些数值比较器还可以将给定的机器数按照补码编码进行有符号数比较

\subsubsection{一般比较器}

若只需要获知是否相等，则直接逐位异或即可，如图 \ref{fig:不同位宽的比较器} 所示
\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.72\textwidth]{figures/相等比较器.png}
    \caption{不同位宽的并行比较器}
    \label{fig:不同位宽的比较器}
\end{figure}

图 \ref{fig:不同位宽的比较器} 中所示为并行比较器，速度较快\\
使用迭代电路同样可以实现迭代比较器，从高位依次比较至低位，速度较慢

\subsubsection{数值比较器}
常用数值比较器如图 \ref{fig:两种数值比较器与输出逻辑} 所示，注意高位在下侧输入\\
对于图中8位宽数值比较器，输出只与输入的两数字的大小关系有关\\
对于图中74x85数值比较器，输出还与其它三个输入端口，用于级联
\begin{figure}[htpb]
    \centering
    \begin{tabular}{ccc}
        \multirow{11}{*}{
        \includegraphics[width=0.20\textwidth]{figures/数值比较器8bit.png} 
        \includegraphics[width=0.25\textwidth]{figures/比较器74x85.png}} &
        \multirow{11}{*}{$\begin{aligned}
            &\text{74x85 \kaishu 数值比较器的输入输出逻辑：}\\
            &\mathtt{AGTBOUT} = (A>B) + (A=B) \cdot \mathtt{AGTBIN}\\
            &\mathtt{AEQBOUT} = (A=B) \cdot \mathtt{AEQBIN}\\
            &\mathtt{ALTBOUT} = (A<B) + (A=B) \cdot \mathtt{ALTBIN}
        \end{aligned}$}& \\
        & &\\ & &\\ & &\\ & &\\ & &\\ & &\\ & &\\ & &\\ & &\\ & &\\
    \end{tabular}
    \caption{两种数值比较器与输出逻辑}
    \label{fig:两种数值比较器与输出逻辑}
\end{figure}

对于图 \ref{fig:两种数值比较器与输出逻辑} 中74x85数值比较器，输入本片的 $A,B$ 大小关系先于级联端口决定输出\\
因此级联时应当将低位比较结果连接到高位比较器的级联端口，如图 \ref{fig:比较器74x85级联}，注意高位在末端比较
\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.95\textwidth]{figures/比较器74x85串联.png}
    \caption{比较器{\upshape 74x85}级联}
    \label{fig:比较器74x85级联}
\end{figure}

对于图 \ref{fig:两种数值比较器与输出逻辑} 中的8位宽比较器，虽无级联端口但也可以级联，
如图 \ref{fig:三个8位宽数值比较器级联为22位宽}\\
基本原理是用本片的最低两位来表示更低位的大小关系（{\kaishu 右下最高位}）

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.9\textwidth]{figures/数值比较器的级联.png}
    \caption{三个8位宽数值比较器级联为22位宽}
    \label{fig:三个8位宽数值比较器级联为22位宽}
\end{figure}

图 \ref{fig:三个8位宽数值比较器级联为22位宽} 中所示方法在级联级数较多时会显著增大延迟\\
可以改用如图 \ref{fig:九个8位宽数值比较器树状扩展为64位宽} 所示树状结构\\

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.7\textwidth]{figures/九个8位宽数值比较器树状扩展为64位宽.pdf}
    \caption{九个8位宽数值比较器树状扩展为64位宽}
    \label{fig:九个8位宽数值比较器树状扩展为64位宽}
\end{figure}

图 \ref{fig:数值比较器逻辑电路图} 展示了8位宽数值比较器的内部结构\\
上侧电路用来比较是否相等\\
下侧电路用来比较 $P$ 是否大于 $Q$\\
从上两个结果中可以获悉 $P$ 是否小于 $Q$

\begin{figure}[H]
    \centering
    \includegraphics[width=0.99\textwidth]{figures/数值比较器逻辑电路图.pdf}
    \caption{8位宽数值比较器逻辑电路图}
    \label{fig:数值比较器逻辑电路图}
\end{figure}

\subsection{加法器与减法器}
\subsubsection{半加器与全加器}
半加器：输入两个1bit加数\texttt{A,B}，输出半加和 \texttt{HS} 与给高位的进位 \texttt{COUT}\\
全加器：输入两个1bit加数\texttt{A,B}与从低位的进位 \texttt{CIN}，输出全加和 \texttt{S} 与给高位的进位 \texttt{COUT}
\begin{align*}
    \mathtt{S} &= \mathtt{A \oplus B \oplus CIN} \\
               &= \mathtt{A \cdot B' \cdot CIN' + A' \cdot B \cdot CIN' + A' \cdot B' \cdot CIN + A \cdot B \cdot CIN}\\
    \mathtt{COUT} &= \mathtt{A \cdot B + A\cdot CIN + B\cdot CIN}
\end{align*}

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.75\textwidth]{figures/全加器逻辑电路与符号.png}
    \caption{全加器逻辑电路与符号}
    \label{fig:全加器逻辑电路与符号}
\end{figure}

\subsubsection{串行进位加法器 ripple adder}
$n$ 个全加器级联成为 $n$ 位宽串行进位加法器，如图 \ref{fig:串行进位加法器及其延迟计算} 所示，其延迟为：
$$
t_{\rm ADD} = t_{\text{\texttt{AB-Cout}}} + (n-2)t_{\text{\texttt{Cin-Cout}}} + t_{\text{\texttt{Cin-S}}}
$$
\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.7\textwidth]{figures/串行进位加法器及其延迟计算.png}
    \caption{串行进位加法器及其延迟计算}
    \label{fig:串行进位加法器及其延迟计算}
\end{figure}

\subsubsection{先行进位加法器}
%先行进位(carry lookahead) 的基本思想：\\
加法器（不必限制为1bit）有两种输入：两组加数$a,b$、低位进位$c_{\rm in}$\\
可能仅从两组加数就可以确定将给高位进位，称\emph{进位生成}\\
可能仅从两组加数就可以确定不给高位进位\\
否则一定是 $c_{\rm in}=1$ 可以触发从低位到高位的每一位都进位，称为\emph{进位传递}

这样分组是因为 $a,b$ 是初始给定的，而 $c_{\rm in}$ 需要等待低位运算结果\\
先行进位的基本思想就是将 $c_{\rm in}$ 直接用低位的 $a,b$ 与 $c_0$ 表示，用额外的电路快速得到所有位的 $c_{\rm in}$

下面考虑 1 bit 加法器的具体情况：\\
对于第 $i$ 位全加器，记$c_i=c_{\rm in}$
\begin{enum}
\item 若两个加数均为 1，则 $c_{i+1}=1$（\emph{进位生成}，记为 $g_i$）
\item 若两个加数均为 0，则 $c_{i+1}=0$
\item 若一个为1一个为0，则 $c_{i+1}=c_{i}$（\emph{进位传递}，记为 $p_i$）
\end{enum}

也就是说，想要 $c_{i+1}=1$ 只有进位生成或进位传递两种可能
$$
\begin{aligned}
    g_i &= a_i \cdot  b_i \\
    p_i &= a_i \oplus b_i
\end{aligned}
\qquad\Longrightarrow\qquad 
c_{i+1} = g_i + p_i \cdot c_{i}
$$

注意到：在 $a_i \cdot b_i=1$ 时 $p_i$ 的值无影响，可以人为改为下式（{\kaishu 这时的$p_i$也称为进位激活}）
$$
\begin{aligned}
    g_i &= a_i \cdot  b_i \\
    p_i &= a_i + b_i
\end{aligned}
\qquad\Longrightarrow\qquad 
c_{i+1} = g_i + p_i \cdot c_{i}
$$

将 $c_1$ 至 $c_4$ 展开得到如下表达式，可见都是二级“与-或”表达式
$$
\begin{aligned}
{c}_{1} &={g}_{0}+{p}_{0} \cdot {c}_{0} \\
{c}_{2} &={g}_{1}+{p}_{1} \cdot {c}_{1} \\
&={g}_{1}+{p}_{1} \cdot\left({g}_{0}+{p}_{0} \cdot {c}_{0}\right) \\
&={g}_{1}+{p}_{1} \cdot {g}_{0}+{p}_{1} \cdot {p}_{0} \cdot {c}_{0} \\
{c}_{3} &={g}_{2}+{p}_{2} \cdot {c}_{2} \\
&={g}_{2}+{p}_{2} \cdot\left({g}_{1}+{p}_{1} \cdot {g}_{0}+{p}_{1} \cdot {p}_{0} \cdot {c}_{0}\right) \\
&={g}_{2}+{p}_{2} \cdot {g}_{1}+{p}_{2} \cdot {p}_{1} \cdot {g}_{0}+{p}_{2} \cdot {p}_{1} \cdot {p}_{0} \cdot {c}_{0} \\
{c}_{4} &={g}_{3}+{p}_{3} \cdot {c}_{3} \\
&={g}_{3}+{p}_{3} \cdot\left({g}_{2}+{p}_{2} \cdot {g}_{1}+{p}_{2} \cdot {p}_{1} \cdot {g}_{0}+{p}_{2} \cdot {p}_{1} \cdot {p}_{0} \cdot {c}_{0}\right) \\
&={g}_{3}+{p}_{3} \cdot {g}_{2}+{p}_{3} \cdot {p}_{2} \cdot {g}_{1}+{p}_{3} \cdot {p}_{2} \cdot {p}_{1} \cdot {g}_{0}+{p}_{3} \cdot {p}_{2} \cdot {p}_{1} \cdot {p}_{0} \cdot {c}_{0}
\end{aligned}
$$

\begin{quote}
    这个表达式很容易理解，例如 $c_4=1$ 一定表明有某些确定的值被传递到 $c_4$ 使之为1\\
    若 $g_3=1$ 则 $c_4=1$\\
    若 $g_2=1$ 且传递链路通畅则 $c_4=1$\\
    若 $g_1=1$ 且传递链路通畅则 $c_4=1$\\
    若 $g_0=1$ 且传递链路通畅则 $c_4=1$\\
    若 $c_0=1$ 且传递链路通畅则 $c_4=1$\\
    若进位生成、进位传递作为唯二的途径都不能使得 $c_4=1$，则 $c_4=0$
\end{quote}

综上，第 $0\sim3$ 级加法器完成进位所需要的步骤均为：
\begin{enum}
    \item 依据 $a_i,b_i$ 进行与/或运算得到 $g_i,p_i$
    \item 依据 $g_i,p_i,c_0$ 进行与运算
    \item 对上一步的结果进行或运算得到 $c_{i+1}$
\end{enum}

可见，第 $0\sim3$ 级加法器的进位可以在3次与或门延迟后全部完成，不再依赖串行进位\\
在获知本级的 $c_i$ 即 $c_{\rm in}$ 后，可通过如下方式来计算本级全加输出 $s_i$
\begin{align*}
    a_i \oplus b_i &= a_i'\cdot b_i + a_i \cdot b_i' &
               s_i &= a_i \oplus b_i \oplus c_i\\
                   &= g_i' \cdot p_i' &
                   &= (g_i' \cdot p_i) \oplus c_i
\end{align*}


由于 $g_i=1$ 时 $p_i=1$，以上算式还可以化为：
$$
\begin{aligned}
    c_{i+1} &= g_i + p_i \cdot c_i = p_i \cdot(g_i + c_i)\\
{c}_{1} &={p}_{0} \cdot\left({g}_{0}+{c}_{0}\right) \\
{c}_{2} &={p}_{1} \cdot\left({g}_{1}+{c}_{1}\right) \\
&={p}_{1} \cdot\left({g}_{1}+{p}_{0} \cdot\left({g}_{0}+{c}_{0}\right)\right) \\
&={p}_{1} \cdot\left({g}_{1}+{p}_{0}\right) \cdot\left({g}_{1}+{g}_{0}+{c}_{0}\right) \\
{c}_{3} &={p}_{2} \cdot\left({g}_{2}+{c}_{2}\right) \\
&={p}_{2} \cdot\left({g}_{2}+{p}_{1} \cdot\left({g}_{1}+{p}_{0}\right) \cdot\left({g}_{1}+{g}_{0}+{c}_{0}\right)\right) \\
&={p}_{2} \cdot\left({g}_{2}+{p}_{1}\right) \cdot\left({g}_{2}+{g}_{1}+{p}_{0}\right) \cdot\left({g}_{2}+{g}_{1}+{g}_{0}+{c}_{0}\right) \\
{c}_{4} &={p}_{3} \cdot\left({g}_{3}+{c}_{3}\right) \\
&={p}_{3} \cdot\left({g}_{3}+{p}_{2} \cdot\left({g}_{2}+{p}_{1}\right) \cdot\left({g}_{2}+{g}_{1}+{p}_{0}\right) \cdot\left({g}_{2}+{g}_{1}+{g}_{0}+{c}_{0}\right)\right) \\
&={p}_{3} \cdot\left({g}_{3}+{p}_{2}\right) \cdot\left({g}_{3}+{g}_{2}+{p}_{1}\right) \cdot\left({g}_{3}+{g}_{2}+{g}_{1}+{p}_{0}\right) \cdot\left({g}_{3}+{g}_{2}+{g}_{1}+{g}_{0}+{c}_{0}\right)
\end{aligned}
$$


4位宽先行进位加法器74x283就利用了上述表达式\\
其逻辑电路如图 \ref{fig:先行进位加法器逻辑电路图} 所示，其中 ${\rm hs}_i=a_i\oplus b_i$ 是半加结果

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.99\textwidth]{figures/先行进位加法器逻辑电路图.pdf}
    \caption{4 bit先行进位加法器74x283逻辑电路图}
    \label{fig:先行进位加法器逻辑电路图}
\end{figure}

构建更大位宽的先行进位加法器会需要有极多输入的与非门，难以构造\\
可以使用多个先行进位模块共同使用，形成组间串行进位加法器或组间先行进位加法器

\subsubsection{组间串行进位加法器}
直接将多个先行进位加法器模块串联即可得到组间串行进位加法器，如图 \ref{fig:组间串行进位加法器逻辑电路} 所示
\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.7\textwidth]{figures/组间串行进位加法器.pdf}
    \caption{16 bit组间串行进位加法器逻辑电路图}
    \label{fig:组间串行进位加法器逻辑电路}
\end{figure}

\subsubsection{组间先行进位加法器}
与串行进位加法器改造成先行进位加法器的过程相似，分为进位生成与进位传递\\
模块整体的进位生成是由其内部的进位生成组成的
$$
\mathtt{Gg} = g_3 + p_3 \cdot g_2 + p_3 \cdot p_2 \cdot g_1 + p_3 \cdot p_2 \cdot p_1 \cdot g_0
$$
若不能进位生成，则给是否能给高位进位却决于 $\mathtt{C0}$ 的进位传递
$$
\mathtt{Pg} = p_3 \cdot p_2 \cdot p_1 \cdot p_0
$$
将进位生成与进位传递组装成给高位的进位输出：$\mathtt{Cg}_{i+1} = \mathtt{Gg}_i + \mathtt{Pg}_i \cdot \mathtt{C0}_i$
$$
\begin{aligned}
&\mathtt{Cg} 1=\mathtt{Gg} 0+\mathtt{Pg} 0 \cdot \mathtt{Cg} 0 \\
&\mathtt{Cg} 2=\mathtt{Gg} 1+\mathtt{Pg} 1 \cdot \mathtt{Gg} 0+\mathtt{Pg} 1 \cdot \mathtt{Pg} 0 \cdot \mathtt{Cg} 0 \\
&\mathtt{Cg} 3=\mathtt{Gg} 2+\mathtt{Pg} 2 \cdot \mathtt{Gg} 2+\mathtt{Pg} 2 \cdot \mathtt{Pg} 1 \cdot \mathtt{Gg} 0+\mathtt{Pg} 2 \cdot \mathtt{Pg} 1 \cdot \mathtt{Pg} 0 \cdot \mathtt{Gg} 0
\end{aligned}
$$
只要每个模块都输出自己的 $\mathtt{Gg}_i$ 与 $\mathtt{Cg}_i$ 就可以另加先行进位电路一次性计算出所有模块所需 \texttt{C0}，
如图 \ref{fig:组间先行进位加法器逻辑电路图}

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.83\textwidth]{figures/组间先行进位加法器.pdf}
    \caption{16 bit组间先行进位加法器逻辑电路图}
    \label{fig:组间先行进位加法器逻辑电路图}
\end{figure}


这样的扩展方式可以重复：\\
将图 \ref{fig:组间先行进位加法器逻辑电路图} 整体封装成为16 bit加法器，
并在先行进位电路中引出16 bit加法器整体的 \texttt{Gg,Pg}\\
利用4个这样的16 bit加法器与一个先行进位电路就可以制造64 bit二级组间先行进位加法器

\subsubsection{并行前缀加法器}
并行前缀加法器是对先行进位思想进一步抽象而来，先行进位加法器主要包括如下三步：
\begin{enum}
    \item 生成前缀：对加数$a,b$ 运算得到进位生成信号 $g_i$ 与进位传递信号 $p_i$
    \item 先行进位：对 $g_i,p_i$ 运算得到所有 $c_{i+1}$
    \item 求全加和：将半加和与 $c_i$ 异或得到全加和
\end{enum}

如图 \ref{fig:先行前缀加法器通用原理图} 展示了先行前缀加法器的通用原理图\\
图中 $p_i$ 采用了异或版本，这样半加和 $\texttt{HS}_i=p_i$，这在VLSI与ASIC中采用较多\\
也可 $p_i=a_i + b_i$ 则半加和 $\texttt{HS}_i = g_i' \cdot p_i$

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.95\textwidth]{figures/先行前缀加法器通用原理图.pdf}
    \caption{并行前缀加法器通用原理图}
    \label{fig:先行前缀加法器通用原理图}
\end{figure}

图中的prefix tree是主要部件，依据 $a_i,b_i$ 所生成的 $g_i,p_i$，加上 $c_{\rm in,0}$ 来计算各个进位\\
与先行进位加法器不同，这里不直接将 $c_{i+1}$ 展开为 $a_i,b_i,c_0$\\
若要计算 $c_{i+1}$ 可以先计算出从第0位到第 $i$ 位总体的 $G_i,P_i$\\
若要计算 $G_i,P_i$ 可以将第0至 $i$ 位分为两部分，先分别计算其 $G_1,P_1,G_0,P_0$
$$
\begin{aligned}
    G_i &= G_1 + P_1 \cdot G_0\\
    P_i &= P_1 \cdot P_0
\end{aligned}
\qquad\Longrightarrow\qquad 
c_{i+1} = G_i + P_i \cdot c_0
$$
需要两种电路作为结点，如图 \ref{fig:并行前缀电路的两种结点} 所示
\begin{enum}
    \item 将两个小位宽加法器的 $G,P$ 联合为一个更大位宽加法器的 $G,P$
    \item 依据一个横跨第0至 $i$ 位的加法器的 $G,P$ 计算 $c_{i+1}$
\end{enum}

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.7\textwidth]{figures/并行前缀电路的两种结点.png}
    \caption{并行前缀电路的两种结点}
    \label{fig:并行前缀电路的两种结点}
\end{figure}

依据如何分步得到横跨第0至$i$ 位的加法器的 $G,P$，有很多种并行前缀加法器\\
Kogge-Stone 并行前缀加法器是其中一种\\
其结点分布如图 \ref{fig:kogge-stone并行前缀电路}，浅色结点用来求 $GP$，深色结点用来求 $c_{i+1}$\\
其工作流程如图 \ref{fig:kogge-stone并行前缀电路工作流程}，方框代表一定位宽的加法器，深色代表已经求出 $c_{\rm in}$

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.99\textwidth]{figures/kogge-stone并行前缀电路.pdf}
    \caption{kogge-stone并行前缀电路}
    \label{fig:kogge-stone并行前缀电路}
\end{figure}

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.8\textwidth]{figures/togge-stone并行前缀电路工作流程.pdf}
    \caption{kogge-stone并行前缀电路工作流程}
    \label{fig:kogge-stone并行前缀电路工作流程}
\end{figure}


\subsubsection{减法器}
全减器：输入被减数 \texttt{A}、减数 \texttt{B}、给低位借位 \texttt{BIN}，输出差 \texttt{D}、从高位借位 \texttt{BOUT}
$$
\begin{aligned}
    \mathtt{D} &= \mathtt{A\oplus B\oplus BIN}\\
    \mathtt{BOUT} &= \mathtt{A'\cdot B + A'\cdot BIN + B\cdot BIN}
\end{aligned}
\qquad\Longrightarrow\qquad 
\begin{aligned}
    \mathtt{D} &= \mathtt{A\oplus B'\oplus BIN'}\\
    \mathtt{BOUT'} &= \mathtt{A\cdot B' + A\cdot BIN' + B'\cdot BIN'}
\end{aligned}
$$

与全加器的逻辑表达式相互比较可知：
任何全加器可添加三个反相器成为全减器\\
也可直接对全加器电路的引脚改名，成为有部分Active Low引脚的全减器\\
如图 \ref{fig:将全加器改造成全减器} 所示，图中内部黑色矩形（以及右图中紧贴的反相圈）表示相同的全加器的物理电路

\begin{figure}[htpb]
    \centering
    \begin{tikzpicture}
        \renewcommand{\myvarx}{2}
        \renewcommand{\myvary}{1.5}
        %\draw[thick] (0,0) rectangle (\myvarx,\myvary);
        %\draw[-latex] (0,\myvary*0.5) node[right]{\texttt{COUT}} -- ++(-1,0);
        %\draw[-latex] (\myvarx+1,\myvary*0.5)  -- (\myvarx,\myvary*0.5) node[left]{\texttt{CIN}};
        %\draw[-latex] (\myvarx/3*1,\myvary+0.5) -- (\myvarx/3*1,\myvary) node[below]{\texttt{A}};
        %\draw[-latex] (\myvarx/3*2,\myvary+0.5) -- (\myvarx/3*2,\myvary) node[below]{\texttt{Y}};
        %\draw[-latex] (\myvarx/2,0) node[above]{\texttt{S}} -- ++(0,-0.5) ;
        %\draw[blue] (\myvarx/2,-0.5) node[below]{\kaishu 全加器};
        \begin{scope}[shift={(\myvarx+2.5,0)}]
            \draw[thick] (0,0) rectangle (\myvarx,\myvary);
            \draw (0,\myvary*0.5) node[right]{\texttt{COUT}} -- (-1.2,\myvary/2);
            \draw[-latex] (\myvarx+1.1,\myvary*0.5)  -- (\myvarx,\myvary*0.5) node[left]{\texttt{CIN}};
            \draw[-latex] (\myvarx/3*1,\myvary+0.5) -- (\myvarx/3*1,\myvary) node[below]{\texttt{A}};
            \draw[-latex] (\myvarx/3*2,\myvary+0.5) -- (\myvarx/3*2,\myvary) node[below]{\texttt{Y}};
            \draw[-latex] (\myvarx/2,0) node[above]{\texttt{S}} -- ++(0,-1.5) node[above left]{\texttt{D}};
            \draw[blue] (\myvarx+2,0-1) node[above left]{\kaishu 全减器};
            \draw[very thick, blue] (-2,-1) rectangle (\myvarx+2,\myvary+1.5);
            \draw[blue]  (0,\myvary/2)         node[above left ] {\texttt{BOUT\_L}};
            \draw[blue]  (\myvarx,\myvary*0.5) node[above right] {\texttt{BIN\_L }};
            \draw[blue]  (\myvarx/3*1,\myvary) node[above left ] {\texttt{{\color{white}\_}A}};
            \draw[blue]  (\myvarx/3*2,\myvary) node[above right] {\texttt{B\_L}};
            \draw[thick] (-1.9,\myvary/2) -- ++(0.5,0.25) -- ++(0,-0.5) -- cycle;
            \draw[thick] (-1.3,\myvary/2) circle[radius=0.1];
            \draw[-latex](-1.9,\myvary/2) -- ++(-1.2,0) node[above right]{\texttt{\texttt{BOUT}}};
            \draw[thick] (\myvarx+1.2,\myvary/2) circle[radius=0.1];
            \draw[thick] (\myvarx+1.2+0.1,\myvary/2) -- ++(0.5,0.25) -- ++(0,-0.5) -- cycle;
            \draw[-latex](\myvarx+2+1,\myvary/2) node[above left]{\texttt{\texttt{BIN}}} -- (\myvarx+1.2+0.1+0.5,\myvary/2);
            \draw[thick] (\myvarx/3*2,\myvary+0.5+0.1) circle[radius=0.1];
            \draw[thick] (\myvarx/3*2,\myvary+0.5+0.2) -- ++(-0.25,0.5) -- ++(0.5,0) -- cycle;
            \draw (\myvarx/3*2,\myvary+0.5+0.2+0.5) -- (\myvarx/3*2,\myvary+2) node[below right] {\texttt{B}};
            \draw (\myvarx/3*1,\myvary+0.5        ) -- (\myvarx/3*1,\myvary+2) node[below left ] {\texttt{A}};
        \end{scope}
        \begin{scope}[shift={(13,0)}]
            \draw (\myvarx/2,\myvary+1.3) node{\kaishu 直接将全加器引脚更名};
            \draw[thick] (0,0) rectangle (\myvarx,\myvary);
            \draw[-latex] (-0.2,\myvary*0.5) -- ++(-1,0);
            \draw (0,\myvary*0.5) node[right]{\texttt{BOUT}};
            \draw[-latex] (\myvarx+1,\myvary*0.5)  -- (\myvarx+0.2,\myvary*0.5);
            \draw (\myvarx,\myvary*0.5) node[left]{\texttt{BIN}};
            \draw[-latex] (\myvarx/3*1,\myvary+1) -- (\myvarx/3*1,\myvary);
            \draw (\myvarx/3*1,\myvary) node[below]{\texttt{A}};
            \draw[-latex] (\myvarx/3*2,\myvary+1) -- (\myvarx/3*2,\myvary+0.2);
            \draw (\myvarx/3*2,\myvary) node[below]{\texttt{B}};
            \draw[-latex] (\myvarx/2,0) node[above]{\texttt{D}} -- ++(0,-0.5) ;
            \draw[blue] (\myvarx/2,-0.5) node[below]{\kaishu 有部分Active Low引脚的全减器};
            \draw[blue]  (0,\myvary/2)         node[above left ] {\texttt{BOUT\_L}};
            \draw[blue]  (\myvarx,\myvary*0.5) node[above right] {\texttt{BIN\_L }};
            \draw[blue]  (\myvarx/3*1,\myvary) node[above left ] {\texttt{{\color{white}\_}A}};
            \draw[blue]  (\myvarx/3*2,\myvary) node[above right] {\texttt{B\_L}};
            \draw[thick] (\myvarx/3*2,\myvary+0.1) circle[radius=0.1];
            \draw[thick] (\myvarx+0.1,\myvary/2) circle[radius=0.1];
            \draw[thick] (-0.1,\myvary/2) circle[radius=0.1];
        \end{scope}
    \end{tikzpicture}
    \caption{将全加器改造成全减器}
    \label{fig:将全加器改造成全减器}
\end{figure}

串行进位减法器也可由此构建，如图 \ref{fig:串行进位减法器逻辑电路} 所示\\
再次提示：紧贴黑色矩形框的反相圈是全加器物理电路的内部组成部分

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.95\textwidth]{figures/串行进位减法器.png}
    \caption{串行进位减法器逻辑电路}
    \label{fig:串行进位减法器逻辑电路}
\end{figure}

由此再次证实：机器数减法可通过补码运算转化为机器数加法\\
串行进位减法器 = 串行进位加法器(最低位 \texttt{Cin=1}) + 按位取反

\begin{quote}
    用作减法器时，串行进位加法器的最高位 \texttt{Cout} 引脚输出的信号是 \texttt{Bout\_L}\\
    因此证实：最高位\texttt{Cout=0} 意味着 \texttt{Bout=1}，说明无符号数减法溢出
\end{quote}

\subsubsection{加法器应用举例}
\paragraph{BCD码、2421码、余三码互相转换}
此三种BCD编码见表 \ref{tab:三种BCD编码}，由高位到低位分别记为 $ABCD$
\begin{table}[htpb]
    \centering
    \caption{三种BCD编码}
    \label{tab:三种BCD编码}
    \includegraphics[width=0.4\textwidth]{figures/三种BCD编码.png}
\end{table}

8421码转余三码：直接加0011\\
余三码转8421码：直接加1101

2421码转余三码：
最高位$A=0$加0011，最高位$A=1$加1101，也即始终加 $AAA'1$\\
余三码转2421码：始终减 $AAA'1$，也即始终加 $A'A'A1$

8421码与2421码互相转化：四输入四输出卡诺图？


\paragraph{BCD加法器}
若要利用4 bit二进制加法器实现BCD加法，需对求和结果做校正，如表 \ref{tab:BCD加法校正表} 所示

\begin{table}[htpb]
    \centering
    \caption{BCD加法校正表}
    \label{tab:BCD加法校正表}
    \begin{tabular}{c|c|ccccc|ccccc}
        \toprule
        &\multirow{2}{*}{十进制数} & \multicolumn{5}{c|}{未校正的BCD和} & \multicolumn{5}{c}{校正后的BCD和}\\
           & & C4& S3 & S2 & S1 & S0 & C4 & S3 & S2 & S1 & S0 \\  
        \hline
        \multirow{5}{*}{\kaishu\shortstack{无\\需\\校\\正}} & 0  & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\  
                                                     &  1 &  0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 
        &$\vdots$ &  $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ \\ 
                                                     &  8 &  0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 
                                                     &  9 &  0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 \\ 
        \hline
           \multirow{9}{*}{\kaishu\shortstack{需\\要\\校\\正}}& 10 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 
           & 11 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ 
           & 12 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 
           & 13 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 
           & 14 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ 
           & 15 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 0 & 1 \\ 
           \cline{2-12}
           & 16 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 
           & 17 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 1 \\ 
           & 18 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 \\ 
        \bottomrule
    \end{tabular}
\end{table}

当计算结果处于 $10\sim18$ 之间时将结果加0110，否则将结果加0000\\
首先判断结果是否需要校正（{\kaishu 利用卡诺图}）
$$
A = C_4' \cdot (S_3S_2+S_3S_1) + C_4 = C_4 + S_3S_2 + S_3S_1
$$

再对结果进行校正即可：
\begin{align*}
    \mathtt{S_3S_2S_1S_0} &\coloneqq \mathtt{S_3S_2S_1S_0 + 0AA0}\\
        \mathtt{C_4}      &\coloneqq \mathtt{A}
\end{align*}

\paragraph{两位BCD码转二进制}
两位BCD码$B_{80}B_{40}B_{20}B_{10}B_8B_4B_2B_1$转化为二进制 $A_7A_6A_5A_4A_3A_2A_1A_0$
\begin{align*}
    D &= B_{80} \times 80 + B_{40} \times 40 + B_{20} \times 20 + B_{10} \times 10 
        + B_{8} \times 8 + B_4 \times 4 + B_2 \times 2 + B_1 \times 1 \\
      &=   (64+16)B_{80} +  (32+8) B_{40} +   (16+4)B_{20} +   (8+2) B_{10} 
        + 8B_{8}   + 4B_4  +2 B_2   + B_1   \\
      &=   2^6B_{80} +   2^5B_{40} +   2^4(B_{80}+B_{20}) +   2^3 (B_{40}+B_{10}+B_8)
        +   2^2(B_{20}+B_4) +   2^1(B_{10}+B_2) + B_1
\end{align*}

需要两个4 bit加法器，如图 \ref{fig:2位BCD转化为二进制数} 所示

\begin{figure}[htpb]
    \centering
    \begin{tikzpicture}
        \renewcommand{\myvarx}{1.8}
        \renewcommand{\myvary}{4.5}
        \draw (\myvarx/2,0) node[below] {74x283};
        \draw[thick] (0,0) rectangle (\myvarx,\myvary);
        \draw (0,\myvary/9*0.5) node[right] {$B_3$};
        \draw (0,\myvary/9*1.5) node[right] {$A_3$};
        \draw (0,\myvary/9*2.5) node[right] {$B_2$};
        \draw (0,\myvary/9*3.5) node[right] {$A_2$};
        \draw (0,\myvary/9*4.5) node[right] {$B_1$};
        \draw (0,\myvary/9*5.5) node[right] {$A_1$};
        \draw (0,\myvary/9*6.5) node[right] {$B_0$};
        \draw (0,\myvary/9*7.5) node[right] {$A_0$};
        \draw (0,\myvary/9*8.5) node[right] {$C_0$};
        \draw (\myvarx,\myvary/9*0.5) node[left] {$C_4$};
        \draw (\myvarx,\myvary/9*1.5) node[left] {$S_3$};
        \draw (\myvarx,\myvary/9*3.5) node[left] {$S_2$};
        \draw (\myvarx,\myvary/9*5.5) node[left] {$S_1$};
        \draw (\myvarx,\myvary/9*7.5) node[left] {$S_0$};
        \draw (0,\myvary/9*0.5) -- ++(-0.6,0) ;
        \draw (0,\myvary/9*1.5) -- ++(-0.6,0) ;
        \draw (0,\myvary/9*2.5) -- ++(-0.6,0) ;
        \draw (0,\myvary/9*3.5) -- ++(-0.6,0) ;
        \draw (0,\myvary/9*4.5) -- ++(-0.6,0) ;
        \draw (0,\myvary/9*5.5) -- ++(-0.6,0) ;
        \draw (0,\myvary/9*6.5) -- ++(-0.6,0) ;
        \draw (0,\myvary/9*7.5) -- ++(-0.6,0) ;
        \draw (0,\myvary/9*8.5) -- ++(-0.6,0) ;
        \draw (-1.5,\myvary/9*0.5) node[anchor=west] {$B_{80}$};
        \draw (-1.5,\myvary/9*1.5) node[anchor=west] {$\,  0 $};
        \draw (-1.5,\myvary/9*2.5) node[anchor=west] {$B_{40}$};
        \draw (-1.5,\myvary/9*3.5) node[anchor=west] {$B_{ 8}$};
        \draw (-1.5,\myvary/9*4.5) node[anchor=west] {$B_{20}$};
        \draw (-1.5,\myvary/9*5.5) node[anchor=west] {$B_{ 4}$};
        \draw (-1.5,\myvary/9*6.5) node[anchor=west] {$B_{10}$};
        \draw (-1.5,\myvary/9*7.5) node[anchor=west] {$B_{ 2}$};
        \draw (-1.5,\myvary/9*8.5) node[anchor=west] {$\,  0 $};
        \draw (-1.5,\myvary/9*9.5) node[anchor=west] {$B_{ 1}$};
        \begin{scope}[shift={(5,-\myvary/9*4)}]
            \draw (\myvarx/2,0) node[below] {74x283};
            \draw[thick] (0,0) rectangle (\myvarx,\myvary);
            \draw (0,\myvary/9*0.5) node[right] {$B_3$};
            \draw (0,\myvary/9*1.5) node[right] {$A_3$};
            \draw (0,\myvary/9*2.5) node[right] {$B_2$};
            \draw (0,\myvary/9*3.5) node[right] {$A_2$};
            \draw (0,\myvary/9*4.5) node[right] {$B_1$};
            \draw (0,\myvary/9*5.5) node[right] {$A_1$};
            \draw (0,\myvary/9*6.5) node[right] {$B_0$};
            \draw (0,\myvary/9*7.5) node[right] {$A_0$};
            \draw (0,\myvary/9*8.5) node[right] {$C_0$};
            \draw (\myvarx,\myvary/9*0.5) node[left] {$C_4$};
            \draw (\myvarx,\myvary/9*1.5) node[left] {$S_3$};
            \draw (\myvarx,\myvary/9*3.5) node[left] {$S_2$};
            \draw (\myvarx,\myvary/9*5.5) node[left] {$S_1$};
            \draw (\myvarx,\myvary/9*7.5) node[left] {$S_0$};
            \draw (0,\myvary/9*0.5) -- ++(-0.6,0) ;
            \draw (0,\myvary/9*1.5) -- ++(-0.6,0) ;
            \draw (0,\myvary/9*2.5) -- ++(-0.6,0) ;
            \draw (0,\myvary/9*4.5) -- ++(-0.6,0) ;
            \draw (0,\myvary/9*6.5) -- ++(-0.6,0) ;
            \draw (0,\myvary/9*8.5) -- ++(-0.6,0) ;
            \draw (-1.4,\myvary/9*0.5) node[anchor=west] {$B_{80}$};
            \draw (-1.4,\myvary/9*1.5) node[anchor=west] {$\,  0 $};
            \draw (-1.4,\myvary/9*2.5) node[anchor=west] {$B_{40}$};
            \draw (-1.4,\myvary/9*4.5) node[anchor=west] {$B_{20}$};
            \draw (-1.4,\myvary/9*6.5) node[anchor=west] {$B_{10}$};
            \draw (-1.4,\myvary/9*8.5) node[anchor=west] {$\,  0 $};
        \end{scope}
        \draw (\myvarx,\myvary/9*3.5) -- (5,\myvary/9*3.5);
        \draw (\myvarx,\myvary/9*1.5) -- (5,\myvary/9*1.5);
        \draw (\myvarx,\myvary/9*0.5) -- ++(1,0) |- (5,-\myvary/9*0.5);
        \draw (-0.6,\myvary/9*9.5)    -- (5+\myvarx+3,\myvary/9*9.5) node[right] {$A_0$};
        \draw (\myvarx,\myvary/9*7.5) -- (5+\myvarx+3,\myvary/9*7.5) node[right] {$A_1$};
        \draw (\myvarx,\myvary/9*5.5) -- (5+\myvarx+3,\myvary/9*5.5) node[right] {$A_2$};
        \draw (\myvarx+5, \myvary/9*3.5) -- (5+\myvarx+3, \myvary/9*3.5) node[right] {$A_3$};
        \draw (\myvarx+5, \myvary/9*1.5) -- (5+\myvarx+3, \myvary/9*1.5) node[right] {$A_4$};
        \draw (\myvarx+5,-\myvary/9*0.5) -- (5+\myvarx+3,-\myvary/9*0.5) node[right] {$A_5$};
        \draw (\myvarx+5,-\myvary/9*2.5) -- (5+\myvarx+3,-\myvary/9*2.5) node[right] {$A_6$};
        \draw (\myvarx+6,-\myvary/9*4.5) node[left]{0} -- (5+\myvarx+3,-\myvary/9*4.5) node[right] {$A_7$};
    \end{tikzpicture}
    \caption{两位BCD转化为二进制数}
    \label{fig:2位BCD转化为二进制数}
\end{figure}

\subsection{循环移位}
桶形移位器可以实现循环移位操作，可通过多路复用器实现\\
通过单级多个多路复用器实现桶形移位器，如图 \ref{fig:桶形移位器（单级型）} 所示\\
此电路规模较大且输入信号的扇出系数高，但延迟较小

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.65\textwidth]{figures/桶形移位1.png}
    \caption{桶形移位器（单级型）}
    \label{fig:桶形移位器（单级型）}
\end{figure}

也可用多路复用器级联的方式实现，如图 \ref{fig:桶形移位器（级联型）} 所示\\
第一级可进行1位移位，第二级可进行2位移位，第三级可进行4位移位，第四级可进行8位移位\\
按需操控各级MUX便可实现$0\sim 15$ 位移位

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.98\textwidth]{figures/桶形移位2.pdf}
    \caption{桶形移位器（级联型）}
    \label{fig:桶形移位器（级联型）}
\end{figure}

\section{时序逻辑元件}
输出不仅是输入的函数，也是前次状态的函数\\
前次状态通常由反馈回线储存

\subsection{触发器与锁存器}

锁存器(latch)与触发器(flip-flop)： 
\begin{enum}
    \item 锁存器：持续对输入采样，任何时候都可以改变其输出
    \item 触发器：持续对输入采样，但仅在时钟信号边沿改变输出
\end{enum}

\subsubsection{S-R锁存器}
\begin{quote}
S-R：Set-Reset，置位-复位
\end{quote}

S-R锁存器如图 \ref{fig:S-R锁存器逻辑电路与真值表}
\begin{enum}
\item $\mathtt{S,R}$ 均为\texttt{0}，则 $\mathtt Q$ 维持原态
\item $\mathtt{R=1}$ 则置 $\mathtt{Q=0}$
\item $\mathtt{S=1}$ 则置 $\mathtt{Q=1}$
\item $\mathtt{S=1}$ 且 $\mathtt{R=1}$ 时 $\mathtt{Q=QN=0}$。若 $\mathtt{S,R}$ 同时回到\texttt{0}则锁存器进入振荡态或亚稳态
\end{enum}

利用卡诺图得到次态逻辑表达式（$\mathtt{S=R=1}$的情况记为 don't care）
\begin{figure}[htpb]
    \centering
    \begin{tabular}{cc}
        \multirow{5}{*}{\includegraphics[width=0.65\textwidth]{figures/S-R锁存器.png}} &
        \multirow{5}{*}{
        $\quad
        \begin{aligned}
        &\mathtt{Q^*} = \mathtt{S + R' \cdot Q}\\
        &\mathtt{S\cdot R} \ne \mathtt{1}
        \end{aligned}$}\\
        &\\&\\&\\&\\
    \end{tabular}
    \caption{S-R锁存器逻辑电路与真值表}
    \label{fig:S-R锁存器逻辑电路与真值表}
\end{figure}

几种传播延迟：$t_{\rm pLH(\mathtt{SQ})}$，$t_{\rm pHL(\mathtt{RQ})}$，$t_{\rm pLH(\mathtt{SQN})}$，$t_{\rm pHL(\mathtt{RQN})}$\\
最小脉冲宽度：$t_{\rm pw(min)}$，若 \texttt{S,R} 上的脉冲宽度小于此值，可能会使锁存器进入亚稳定状态

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.8\textwidth]{figures/S-R锁存器延迟示意图.png}
    \caption{S-R锁存器延迟时序图}
    \label{fig:S-R锁存器延迟示意图}
\end{figure}


\subsubsection{S'-R'锁存器}

S'-R'锁存器与 S-R锁存器完全相似，只是对外暴露出端口 \texttt{S\_L,R\_L}，如图 \ref{fig:S'-R'锁存器逻辑电路图、真值表、符号} 所示

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.95\textwidth]{figures/S_L-R_L锁存器.png}
    \caption{S'-R'锁存器}
    \label{fig:S'-R'锁存器逻辑电路图、真值表、符号}
\end{figure}

\subsubsection{有使能端的S-R锁存器}

有使能端的 S-R 锁存器如图 \ref{fig:有使能端的SR锁存器} 所示
\begin{enum}
    \item 在 $\mathtt{C=1}$ 时发挥 S-R 锁存器的功能
    \item 在 $\mathtt{C=0}$ 时 $\mathtt{Q^*=Q}$
\end{enum}

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.95\textwidth]{figures/有使能端的SR锁存器.png}
    \caption{有使能端的SR锁存器}
    \label{fig:有使能端的SR锁存器}
\end{figure}

\subsubsection{D锁存器}

在有使能端的S-R锁存器的基础上令 $\mathtt{R=S'}$ 即得 D锁存器，如图 \ref{fig:D锁存器逻辑电路、真值表、符号} 所示
\begin{enum}
\item $\mathtt{C=0}$ 时 $\mathtt{Q^*=Q}$
\item $\mathtt{C=1}$ 时 $\mathtt{Q^*=D}$
\end{enum}

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.95\textwidth]{figures/D锁存器.png}
    \caption{D锁存器}
    \label{fig:D锁存器逻辑电路、真值表、符号}
\end{figure}

传播延迟：$t_{\rm pLH(\mathtt{GQ})}$，$t_{\rm pHL(\mathtt{GQ})}$，$t_{\rm pLH(\mathtt{DQ})}$，$t_{\rm pHL(\mathtt{DQ})}$\\
时间窗口：在\texttt{G}的下降沿之前 $t_{\rm setup}$ 与之后 $t_{\rm hold}$ 时间内\texttt{D}必须维持不变，否则进入亚稳态\\
D锁存器的延迟时序如图 \ref{fig:D锁存器的亚稳态} 所示

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.95\textwidth]{figures/D锁存器的亚稳态.png}
    \caption{D锁存器的延迟时序图}
    \label{fig:D锁存器的亚稳态}
\end{figure}

\subsubsection{边沿 D 触发器}
D 锁存器在 $\mathtt{G=1}$ 时类似于跟随器\\
对于同步时序电路来说希望在时钟周期内储存器输出不变

边沿D触发器逻辑电路如图 \ref{fig:边沿D触发器} 所示
\begin{enum}
    \item 在时钟上升沿，主锁存器锁定\texttt{D}并输送给从锁存器，同时从锁存器开启使 $\mathtt{Q^*=QM=D}$
    \item 在时钟的其它部分 $\mathtt{Q^*=Q}$
\end{enum}

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.95\textwidth]{figures/边沿D触发器.png}
    \caption{边沿D触发器}
    \label{fig:边沿D触发器}
\end{figure}

传播延迟：$t_{\rm pLH(\mathtt{CQ})}$，$t_{\rm pHL(\mathtt{CQ})}$\\
时间窗口：在\texttt{CLK}的上升沿之前 $t_{\rm setup}$ 与之后 $t_{\rm hold}$ 时间内\texttt{D}必须维持不变，否则进入亚稳态\\
D触发器的延迟时序如图 \ref{fig:D触发器延迟时序图} 所示

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.95\textwidth]{figures/D触发器延迟时序图.png}
    \caption{D触发器延迟时序图}
    \label{fig:D触发器延迟时序图}
\end{figure}

\subsubsection{有异步输入端的D触发器}
有些D触发器有异步输入端，可以不拘于\texttt{CLK}来控制 \texttt{Q}，通常用于初始化
\begin{enum}
    \item \texttt{PR} ：异步置位$\mathtt{Q^*=1}$
    \item \texttt{CLR}：异步清零$\mathtt{Q^*=0}$
\end{enum}

有异步输入端的D触发器如图 \ref{fig:异步使能边沿D触发器}

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.95\textwidth]{figures/异步使能边沿D触发器.png}
    \caption{有异步输入端的D触发器}
    \label{fig:异步使能边沿D触发器}
\end{figure}

\subsubsection{有使能端的D触发器}
本质上是使 $\mathtt{EN=0}$ 时 $\mathtt{Q^* = Q}$，相当于增加一个MUX，如图 \ref{fig:有使能端的D触发器} 所示
\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.95\textwidth]{figures/有使能端的D触发器.png}
    \caption{有使能端的D触发器}
    \label{fig:有使能端的D触发器}
\end{figure}

\subsubsection{Scan触发器}
类似有使能端的D触发器，但MUX在 \texttt{D} 与 \texttt{TI} 中选择一路，如图 \ref{fig:Scan触发器} 所示

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.95\textwidth]{figures/Scan触发器.png}
    \caption{Scan触发器}
    \label{fig:Scan触发器}
\end{figure}

Scan触发器通常用于ASIC测试，\texttt{TE,TI} 表示 Test-Enable 和 Test-Input

\subsubsection{主从S-R脉冲触发器}
主从S-R脉冲触发器如图 \ref{fig:主从SR触发器}，注意它并不是边沿触发的\\
例如：只要在 $\mathtt{CLK=1}$ 的区间内有 $\mathtt{S=1}$ 短脉冲，在 \texttt{CLK} 下降沿后 $\mathtt{Q^*=1}$
\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.95\textwidth]{figures/主从SR触发器.png}
    \caption{主从S-R触发器}
    \label{fig:主从SR触发器}
\end{figure}

\subsubsection{主从J-K脉冲触发器}
主从J-K脉冲触发器如图 \ref{fig:主从JK触发器}
\begin{enum}
\item \texttt{Q} 的值仅在 \texttt{CLK} 下降沿更新，但 $\mathtt{Q^*}$ 的值取决于脉冲触发的全过程
\item 脉冲触发时 $\mathtt{J=1}$   则\texttt{CLK}下降沿时 $\mathtt{Q^* = 1}$（$\mathtt{Q=1}$ 时无效）
\item 脉冲触发时 $\mathtt{K=1}$   则\texttt{CLK}下降沿时 $\mathtt{Q^* = 0}$（$\mathtt{Q=0}$ 时无效）
\item 脉冲触发时 $\mathtt{J=K=1}$ 则\texttt{CLK}下降沿时 $\mathtt{Q^* = Q'}$（\texttt{J,K} 两者中总有一个无效）
\item 脉冲触发时未出现 \texttt{J,K} 非零值，$\mathtt{Q^*=Q}$
\end{enum}

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.95\textwidth]{figures/主从JK触发器.png}
    \caption{主从J-K脉冲触发器}
    \label{fig:主从JK触发器}
\end{figure}

主从J-K脉冲触发器的功能时序如图 \ref{fig:主从JK触发器功能时序图} 所示\\
注意最后两个波形变化，分别称为0钳位与1钳位

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.95\textwidth]{figures/主从JK触发器功能时序图.png}
    \caption{主从J-K脉冲触发器功能时序图}
    \label{fig:主从JK触发器功能时序图}
\end{figure}

\subsubsection{J-K边沿触发器}
利用D触发器也可构建J-K功能的触发器，且为边沿触发，其它功能与主从J-K脉冲触发器完全相同，如图 \ref{fig:JK边沿触发器}
\begin{enum}
\item \texttt{CLK} 上升沿处 $\mathtt{J=1}$ 则 $\mathtt{Q^*=1}$
\item \texttt{CLK} 上升沿处 $\mathtt{K=1}$ 则 $\mathtt{Q^*=0}$
\item \texttt{CLK} 上升沿处 $\mathtt{J=K=1}$ 则 $\mathtt{Q^*=Q}$
\item 由于是边沿触发，不存在0钳位、1钳位的问题
\end{enum}

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.95\textwidth]{figures/JK边沿触发器.png}
    \caption{J-K边沿触发器}
    \label{fig:JK边沿触发器}
\end{figure}

\subsubsection{T触发器}
T触发器的逻辑电路图如图 \ref{fig:有使能端的T触发器}, \ref{fig:有使能端的T触发器} 所示
\begin{enum}
    \item 若 $\mathtt{EN=1}$ 则在每个时钟上升沿 $\mathtt{Q^*=Q'}$
    \item 若 $\mathtt{EN=0}$ 则 $\mathtt{Q^*=Q}$
\end{enum}

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.6\textwidth]{figures/T触发器的两种逻辑电路.png}
    \caption{T触发器的两种逻辑电路}
    \label{fig:T触发器的两种逻辑电路}
\end{figure}

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.7\textwidth]{figures/有使能端的T触发器.png}
    \caption{有使能端的T触发器的两种逻辑电路}
    \label{fig:有使能端的T触发器}
\end{figure}

\subsubsection{锁存器/触发器总结}
各类锁存器/触发器的次态方程如表 \ref{tab:各类锁存器/触发器次态方程} 所示

\begin{table}[H]
    \centering
    \caption{各类锁存器/触发器次态方程}
    \label{tab:各类锁存器/触发器次态方程}
    \begin{tabular}{ll}
        \toprule 
        \makebox[1cm][c]{类型} & \makebox[3.5cm][c]{次态方程} \\
        \midrule
        S-R  & $\mathtt{Q^* = S + R' \cdot Q,\; S\cdot R\ne 0}$\\
        D    & $\mathtt{Q^* = D}$\\
        J-K  & $\mathtt{Q^* = J \cdot Q' + K' \cdot Q}$\\
        T    & $\mathtt{Q^* = Q \oplus EN}$\\
        \bottomrule
    \end{tabular}
\end{table}


\section{状态机}
时序电路的状态是其状态变量的集合\\
想确定 $t>t_0$ 时的状态，最多只需回溯 $t=t_0$ 时的状态，无需考虑 $t<t_0$ 时的状态

通常状态机用D触发器来储存状态变量\\
通常状态机的状态只在时钟信号的跳变沿处更新（时钟同步状态机）

\begin{quote}
    时钟对时序电路的意义？\\
    同步逻辑电路/异步逻辑电路
\end{quote}

\subsection{状态机结构}
Mealy型状态机结构如图 \ref{fig:Mealy型状态机结构} 所示\\
$\text{输出} = f(\text{现态},\;\text{输入})$\\
$\text{次态} = g(\text{现态},\;\text{输入})$，仅在时钟触发沿更新状态\\
注意Mealy型状态机的输出在任何时刻都可随输入变化，不必等待时钟触发

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.8\textwidth]{figures/Mealy型状态机结构.png}
    \caption{Mealy型状态机结构}
    \label{fig:Mealy型状态机结构}
\end{figure}

Moore型状态机结构如图 \ref{fig:Moore型状态机结构} 所示\\
$\text{输出} = f(\text{现态})$\\
$\text{次态} = g(\text{现态},\;\text{输入})$，仅在时钟触发沿更新状态\\
注意Moore型状态机的输出仅取决于现态，实际上仅在时钟触发沿更新输出

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.8\textwidth]{figures/Moore型状态机结构.png}
    \caption{Moore型状态机结构}
    \label{fig:Moore型状态机结构}
\end{figure}

高速电路通常要求状态机尽快产生输出，且输出在时钟周期内保持不变\\
对Moore型状态机将现态不经任何逻辑运算直接输出（以加快输出产生）\\
对Mealy型状态机使上周期的状态与输入成为本周期的输出（以保持输出不变）\\
这样的Mealy机的输出称为流水线型输出，如图 \ref{fig:流水线型输出的Mealy状态机}

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.9\textwidth]{figures/Mealy型流水线输出状态机.png}
    \caption{流水线型输出的Mealy状态机}
    \label{fig:流水线型输出的Mealy状态机}
\end{figure}

各类状态机的时序如图 \ref{fig:各类状态机的时序示意图} 所示，灰色表示信号可能改变\\
只有Mealy型状态机的输出会随输出不遵循时钟改变\\
只有流水线型输出可以与时钟同步改变，但实际上是延迟一整个周期的结果

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.55\textwidth]{figures/各类状态机的时序示意图.png}
    \caption{各类状态机的时序示意图}
    \label{fig:各类状态机的时序示意图}
\end{figure}

\subsection{状态机分析}
同步状态机分析的基本流程如下：
\begin{enum}
    \item 由次态逻辑方程、状态更新方程，得到次态与现态、输入的关系（转移方程）
    \item 依据转移方程列次态真值表
    \item 依据输出逻辑方程向次态真值表中补充输出
    \item 绘制状态图
\end{enum}

举例如图 \ref{fig:状态机分析举例} 所示
\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.98\textwidth]{figures/状态机分析举例.pdf}
    \caption{状态机分析举例：原始逻辑电路图}
    \label{fig:状态机分析举例}
\end{figure}

激励方程（Excitation Equation）与触发器的次态函数
\begin{align*}
    \mathtt {D0} &= \mathtt{EN \cdot Q0' + EN' \cdot Q0} &
    \mathtt{Q0^*} &= \mathtt{D0}\\
    \mathtt {D1} &= \mathtt{EN' \cdot Q1 + EN \cdot Q0 \cdot Q1' + EN \cdot Q0' \cdot Q1} &
    \mathtt{Q1^*} &= \mathtt{D1}
\end{align*}
可得转移方程（次态与现态、输入的关系）（Transition Equation）
\begin{align*}
    \mathtt {Q0^*} &= \mathtt{EN \cdot Q0' + EN' \cdot Q0}\\
    \mathtt {Q1^*} &= \mathtt{EN' \cdot Q1 + EN \cdot Q0 \cdot Q1' + EN \cdot Q0' \cdot Q1}
\end{align*}
列出次态真值表如表 \ref{tab:状态机分析举例：次态与输出真值表} 所示\\
用 $\mathtt{S=A,B,C,D}$ 表示 $\mathtt{Q1Q0}$ 的四种状态\\
依据输出逻辑方程 $\mathtt{MAX} = \mathtt{EN \cdot Q0 \cdot Q1}$ 添加输出
\begin{table}[htpb]
    \centering
    \caption{状态机分析举例：次态与输出真值表}
    \label{tab:状态机分析举例：次态与输出真值表}
    \includegraphics[width=0.75\textwidth]{figures/状态机分析举例_次态真值表.png}
\end{table}

\begin{quote}
    表 \ref{tab:状态机分析举例：次态与输出真值表} 中从左到右依次称为：\\
    迁移表（Transition table），状态表（State table），状态/输出表（State/Output table）
\end{quote}

依据次态真值表可绘制状态迁移图，如图 \ref{fig:状态机分析举例：Mealy机状态图} 所示\\
图中输入 \texttt{EN} 改变时输出 \texttt{MAX} 立即随之改变\\
Mealy 型状态图的输出写在输入旁边，表示输出随时跟随出入变化，但注意状态迁移只在时钟触发沿处进行
\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.6\textwidth]{figures/状态机分析举例_Mealy机状态图.png}
    \caption{状态机分析举例：Mealy机状态图}
    \label{fig:状态机分析举例：Mealy机状态图}
\end{figure}

若将输出逻辑改为 $\mathtt{MAX = Q0 \cdot Q1}$ 则成为 Moore型状态机，
其次态真值表与状态迁移图如图 \ref{fig:状态机分析举例：Moore机次态真值表与状态图} 所示\\
其输出只与现态有关，因此输出 \texttt{MAX} 直接写在表示状态的圆圈中
\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.85\textwidth]{figures/状态机分析举例_Moore机次态真值表与状态图.png}
    \caption{状态机分析举例：Moore机次态真值表与状态图}
    \label{fig:状态机分析举例：Moore机次态真值表与状态图}
\end{figure}


\subsection{状态机设计}
同步状态机的基本设计流程如下：
\begin{enum}
    \item 依据需求设计状态与输出，编制状态表、状态图
    \item 状态化简
    \item 状态分配：例如将状态 $A$ 指定为 \texttt{110} 或是 \texttt{000}
    \item 建立状态变量迁移表
    \item 触发器选型：通常为D触发器
    \item 得到激励表，利用卡诺图得到激励方程，得到次态激励电路
    \item 绘制逻辑电路图
\end{enum}

举例如下：\\
设计具有两个输入 $A,B$ 和一个输出 $Z$ 的状态机，$Z=1$ 的条件是：\\
❶\ 在前两个时钟触发沿上 $A$ 的值相同，或者\\
❷\ 自上一次条件❶为真起，$B$ 始终为1\\
否则 $Z=0$

\subsubsection{设计状态表}
依据给定条件，逐步写出状态表，如图 \ref{fig:状态机设计举例：状态表} 所示
\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.95\textwidth]{figures/状态机设计举例_状态表1.png}
    \includegraphics[width=0.95\textwidth]{figures/状态机设计举例_状态表2.png}
    \caption{状态机设计举例：状态表}
    \label{fig:状态机设计举例：状态表}
\end{figure}

\subsubsection{状态化简}
等价状态：输出相同且状态迁移等价\\
状态迁移等价分为如下几种，举例如表 \ref{tab:状态化简举例} 所示
\begin{enum}
    \item 次态相同：如 $\rm B=D$
    \item 次态都迁移到自己
    \item 次态交错：$\rm F$迁移到$\rm G$，而$\rm G$迁移到$\rm F$
    \item 隐含交错：若$\rm A=C$需$\rm B=D$而$\rm B=D$需$\rm A=C$，那么可令$\rm A=C$且$\rm B=D$
    \item 等价传递：若$\rm B=D$且$\rm B=E$则$\rm B=D=E$
\end{enum}

\begin{table}[htpb]
    \centering
    \caption{状态化简举例}
    \label{tab:状态化简举例}
    \setlength\tabcolsep{0.8cm}
    \begin{subtable}[t]{0.4\linewidth}
        \centering
        \caption{原始状态表}
        \begin{tabular}{c|cc}
        \toprule
            \multirow{2}{*}{S} & \multicolumn{2}{c}{X} \\
        \cline{2-3}
                               & 0 & 1 \\
        \hline
            A & B/0 & C/0 \\
            B & E/1 & C/0 \\
            C & D/0 & A/0 \\
            D & E/1 & A/0 \\
            E & E/1 & C/0 \\
            F & G/1 & E/0 \\
            G & F/1 & E/0 \\
        \bottomrule
        \end{tabular}
    \end{subtable}
    \begin{subtable}[t]{0.4\linewidth}
        \centering
        \caption{状态化简结果}
        \begin{tabular}{c|cc}
        \toprule
            \multirow{2}{*}{S} & \multicolumn{2}{c}{X} \\
        \cline{2-3}
                               & 0 & 1 \\
        \hline
            A & B/0 & A/0 \\
            B & B/1 & A/0 \\
            F & F/1 & B/0 \\
        \bottomrule
        \end{tabular}
    \end{subtable}
\end{table}

\subsubsection{状态赋值}
一些状态赋值的经验性建议：
\begin{enum}
    \item 初始状态为全0或全1
    \item 在状态迁移时将发生改变的状态变量的数目最小化
    \item 对一组关联性较大的状态采用相近的编码
    \item 若有两组状态具有对称性，则采用类似的编码（仅有一位不同）
    \item 将状态变量分组并赋予其确定的含义
    \item 可以考虑使用更多的状态，实现状态分解赋值
    \item 对于未使用的状态，其状态迁移可以是don't care或是Init，在成本与稳定性中做抉择
\end{enum}

本例中可能的状态赋值如表 \ref{tab:状态机设计举例：状态赋值方案} 所示
\begin{enum}
    \item 最简赋值：简单地按照二进制数的顺序进行状态赋值
    \item 分解赋值：Q1指示Init状态，Q2表示输出，Q3表示上一次接收到的 $A$ 
\end{enum}

\begin{table}[htpb]
    \centering
    \caption{状态机设计举例：状态赋值方案}
    \label{tab:状态机设计举例：状态赋值方案}
    \includegraphics[width=0.7\textwidth]{figures/状态机设计举例_状态赋值.png}
\end{table}


\section{时序电路设计实践}
\subsection{时序要求}
时序电路的时序要求如图 \ref{fig:时序电路时序要求} 所示
$$
t_{\rm ffpd} + t_{\rm comb} + t_{\rm setup} < t_{\rm clk}
$$

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.7\textwidth]{figures/时序电路时序要求.png}
    \caption{时序电路时序要求}
    \label{fig:时序电路时序要求}
\end{figure}

\subsection{时序电路举例}
\subsubsection{机械开关消抖}
%机械开关闭合过程中在触点与悬空之间抖动几次，时间在 $10\sim 20\;{\rm ms}$ 之间\\
最简单的消抖电路利用双稳态元件，如图 \ref{fig:最简单的开关消抖电路} 所示\\
开关接触触点时电路状态跟随开关，开关悬空时电路状态维持原状

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.6\textwidth]{figures/开关消抖电路1.png}
    \caption{最简单的开关消抖电路}
    \label{fig:最简单的开关消抖电路}
\end{figure}

\begin{quote}
    图 \ref{fig:最简单的开关消抖电路} 中可见，左半部分没能将抖动完全消除\\
    因为逻辑门输出的低电平并不完全是 $0\;{\rm V}$
\end{quote}

图 \ref{fig:开关消抖电路（S-R锁存器）} 给出了另一种开关消抖电路

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.5\textwidth]{figures/开关消抖电路2.png}
    \caption{开关消抖电路（S-R锁存器）}
    \label{fig:开关消抖电路（S-R锁存器）}
\end{figure}

\subsection{计数器}
\subsubsection{行波计数器}
一般的行波计数器如图 \ref{fig:四种行波计数器} 所示，其中每个T触发器的输出都是输入的二分频\\
优势：电路结构简单、功耗低（只有最低位按照时钟频率工作）\\
劣势：最高位延时高速度低，无法适用于FPGA和PLD

\begin{quote}
    FPGA中所有触发器由相同的时钟信号驱动（\textbf{不确定}）
\end{quote}

\begin{figure}[htpb]
    \centering
    %\includegraphics[width=0.3\textwidth]{figures/行波计数器.png}
    \includegraphics[width=0.9\textwidth]{figures/计数器逻辑电路图.pdf}
    \caption{四种行波计数器}
    \label{fig:四种行波计数器}
\end{figure}

增计数器的低位下降沿处高位翻转\\
减计数器的低位上升沿处高位翻转\\
增计数器的输出取反就是减计数器

\subsubsection{同步计数器}
同步计数器的所有触发器共用相同的\texttt{CLK}信号\\
高位触发器翻转的充要条件：\texttt{CLK}上升沿、低位触发器全为1、使能端\texttt{CNTEN}有效\\
低位触发器的输出要传导至高位，可串行可并行，如图 \ref{fig:同步串行计数器},\ref{fig:同步并行计数器} 所示
\begin{enum}
\item 同步串行计数器：$\mathtt{EN}_{n} = \mathtt{EN}_{n-1} \cdot \mathtt{Q}_{n-1}$ 且最低位 $\mathtt{EN}_0=\mathtt{CNTEN}$
\item 同步并行计数器：$\mathtt{EN}_{n} = \mathtt{CNTEN} \cdot \mathtt{Q}_0 \cdot \cdots \cdot \mathtt{Q}_{n-1}$（速度最快）
\end{enum}

%\begin{quote}
%    减计数器将高位触发器翻转条件改为：
%    \texttt{CLK}上升沿、低位触发器全为0、使能端\texttt{CNTEN}有效
%\end{quote}

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.48\textwidth]{figures/有串行使能端的同步计数器.png}
    \caption{同步串行计数器}
    \label{fig:同步串行计数器}
\end{figure}

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.52\textwidth]{figures/有并行使能端的同步计数器.png}
    \caption{同步并行计数器}
    \label{fig:同步并行计数器}
\end{figure}

\subsubsection{标准MSI计数器}

两种MSI标准计数器的逻辑电路符号如图 \ref{fig:标准MSI计数器} 所示

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.175\textwidth]{figures/74x163计数器.png}
    \qquad
    \includegraphics[width=0.175\textwidth]{figures/74x169计数器.png}
    \caption{标准MSI计数器}
    \label{fig:标准MSI计数器}
\end{figure}

对于74x163计数器，其逻辑电路图如图 \ref{fig:74x163计数器逻辑电路图} 所示，真值表如表 \ref{tab:74x163计数器真值表} 所示
\begin{enum}
\item 同步清零端 \texttt{CLR\_L}
\item 同步置数端 \texttt{LD\_L}
\item 置数数据 \texttt{A,B,C,D}
\item 使能端 \texttt{ENP, ENT}
\end{enum}

对于74x169计数器，其在 \texttt{UP/DN} = 1 时增计数，在 \texttt{UP/DN} = 0 时减计数

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.95\textwidth]{figures/74x163计数器逻辑电路图.pdf}
    \caption{74x163计数器逻辑电路图}
    \label{fig:74x163计数器逻辑电路图}
\end{figure}

在74x163的逻辑电路（图\ref{fig:74x163计数器逻辑电路图}）中：
\begin{enum}
\item 蓝色部分是特化的MUX，其左半部分运算 $A=\mathtt{CLR'\cdot LD}$ 和 $B=A'\cdot\mathtt{LD'} = \mathtt{CLR'\cdot LD'}$\\
    右半部分在 $A=1$ 时输出 \texttt{D[3:0]}，在 $B=1$ 时将粉色部分和D触发器连接为T触发器\\
    在其他时候也就是 $\mathtt{CLR=1}$ 时输出0
\item 粉色部分用来和D触发器构成T触发器
\item 绿色部分用来确定各个T触发器的 \texttt{EN}，详见同步并行计数器
\item 青色部分是元件整体的使能端
\item 红色部分计算 $\mathtt{RCO} = \mathtt{Q_1\cdot Q_2\cdot Q_3 \cdot Q_4\cdot ENT}$，可见 \texttt{ENP} 与 \texttt{ENT} 的唯一差异
\end{enum}

\begin{table}[htpb]
    \centering
    \caption{74x163计数器真值表}
    \label{tab:74x163计数器真值表}
    %\includegraphics[width=0.65\textwidth]{figures/74x163计数器真值表.pdf}
    \includegraphics[width=0.68\textwidth]{figures/74x163计数器真值表.png}
\end{table}

\subsubsection{定时器}
利用增计数器实现定时器，主要分为如下三种
\begin{enum}
\item 下界可调，上界0xF（图 \ref{fig:定时器1}）
\item 下界为0，上界可调（图 \ref{fig:定时器2}）
\item 上下界都可调（图 \ref{fig:定时器3}）
\end{enum}

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.68\textwidth]{figures/定时器1.png}
    \caption{定时器（下界0101，上界1111）}
    \label{fig:定时器1}
\end{figure}
\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.6\textwidth]{figures/定时器2.png}
    \caption{定时器（下界0000，上界1010）}
    \label{fig:定时器2}
\end{figure}
\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.6\textwidth]{figures/定时器3.png}
    \caption{定时器（下界0011，上界1100）}
    \label{fig:定时器3}
\end{figure}

\subsection{移位寄存器}
\subsubsection{移位寄存器的一般结构}
移位寄存器在每个时钟触发沿将所存储的数据移动一位
\begin{enum}
\item 串入串出：将串行信号延迟 $n$ 个周期，如图 \ref{fig:移位寄存器逻辑电路图} 左侧
\item 串入并出：将连续的 $n$ 个串行位转化为 $n$ 位宽并行信号输出，如图 \ref{fig:移位寄存器逻辑电路图} 右侧
\item 并入串出：增加前置MUX，用\texttt{LD/SHIFT}信号来控制移位/并行输入，如图\ref{fig:移位寄存器（并进串出）} 所示
\item 并入并出：与并入串出相似，只是增加了输出端口，如图\ref{fig:移位寄存器（并进串出）} 所示
\end{enum}

\begin{figure}[H]
    \centering
    \includegraphics[width=0.39\textwidth]{figures/移位寄存器_串进串出.png}
    \includegraphics[width=0.34\textwidth]{figures/移位寄存器_串进并出.png}
    \caption{移位寄存器逻辑电路图}
    \label{fig:移位寄存器逻辑电路图}
\end{figure}

\begin{figure}[H]
    \centering
    \includegraphics[width=0.8\textwidth]{figures/移位寄存器_并进串出.png}
    \caption{移位寄存器（并进串出）}
    \label{fig:移位寄存器（并进串出）}
\end{figure}

\begin{figure}[H]
    \centering
    \includegraphics[width=0.8\textwidth]{figures/移位寄存器_并进并出.png}
    \caption{移位寄存器（并进并出）}
    \label{fig:移位寄存器（并进并出）}
\end{figure}

\subsubsection{标准移位寄存器}
某标准移位寄存器逻辑电路如 \ref{fig:标准移位寄存器} 所示，其功能如表 \ref{tab:标准移位寄存器功能表} 所示（$D$ 为低位 $A$ 为高位）
\begin{enum}
\item 同步清零端 \texttt{CLR}
\item 右移串行输入 \texttt{RIN}（实际上是左侧输入） 
\item 左移串行输入 \texttt{LIN}（实际上是右侧输入） 
\item 置数数据端 \texttt{A,B,C,D}
\end{enum}

\begin{table}[H]
    \centering
    \caption{标准移位寄存器功能表}
    \label{tab:标准移位寄存器功能表}
    \includegraphics[width=0.7\textwidth]{figures/标准移位寄存器功能表.png}
\end{table}

\begin{figure}[H]
    \centering
    \includegraphics[width=0.91\textwidth]{figures/标准移位寄存器.pdf}
    \caption{标准移位寄存器}
    \label{fig:标准移位寄存器}
\end{figure}


\subsubsection{移位寄存器型计数器}
将移位寄存器与组合逻辑相连，构成具有循环状态图的状态机，称为移位寄存器型计数器

\paragraph{环形计数器}
4位环形计数器的正常工作状态依次为： 0001, 0010, 0100, 1000\\
对 $n$ 位环形计数器，有 $n$ 个正常状态与$2^n-1$ 个异常状态
\begin{figure}[htpb]
    \centering
    \begin{subfigure}[t]{0.49\textwidth}
        \begin{center}
        \includegraphics[width=0.9\textwidth]{figures/环形计数器（普通）.png}
        \end{center}
        \caption{普通环形计数器}
        \label{fig:普通环形计数器}
    \end{subfigure}
    %\quad
    \begin{subfigure}[t]{0.49\textwidth}
        \begin{center}
        \includegraphics[width=0.9\textwidth]{figures/环形移位寄存器（自校正）.png}
        \end{center}
        \caption{自校正环形计数器}
        \label{fig:自校正环形计数器}
    \end{subfigure}
    \caption{环形移位寄存器逻辑电路图}
    \label{fig:环形移位寄存器逻辑电路图}
\end{figure}

普通环形计数器结构如图 \ref{fig:普通环形计数器} 所示，其状态图如图 \ref{fig:普通环形计数器状态图} 所示\\
此环形计数器的异常状态自成环，不能自行恢复正常，稳健性不佳
\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.95\textwidth]{figures/环形移位寄存器（普通）状态图.png}
    \caption{普通环形计数器状态图}
    \label{fig:普通环形计数器状态图}
\end{figure}

可自校正的环形计数器结构如图 \ref{fig:自校正环形计数器} 所示，其状态图如图 \ref{fig:自校正环形计数器状态图} 所示\\
对 $n$ 位环形计数器，其自校正方式为：非最高位均为 0 时串行输入端为1，否则串行输入端为0


\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.7\textwidth]{figures/环形移位寄存器（自校正）状态图.png}
    \caption{自校正环形计数器状态图}
    \label{fig:自校正环形计数器状态图}
\end{figure}

\paragraph{扭环计数器}

4位扭环计数器的正常循环模式为：0000, 0001, 0011, 0111, 1111, 1110, 1100, 1000, 0000 $\cdots$\\
对 $n$ 位扭环计数器，有 $2n$ 个正常状态与 $2^n-2n$ 个异常状态 \\
两种扭环计数器的逻辑电路结构如图 \ref{fig:扭环计数器逻辑电路图} 所示

\begin{figure}[htpb]
    \centering
    \begin{subfigure}[t]{0.48\textwidth}
        \begin{center}
        \includegraphics[width=0.99\textwidth]{figures/普通扭环移位寄存器.png}
        \end{center}
        \caption{普通扭环计数器}
        \label{fig:普通扭环计数器}
    \end{subfigure}
    \begin{subfigure}[t]{0.45\textwidth}
        \begin{center}
        \includegraphics[width=0.99\textwidth]{figures/自校正扭环移位寄存器.png}
        \end{center}
        \caption{自校正扭环计数器}
        \label{fig:自校正扭环计数器}
    \end{subfigure}
    \caption{扭环计数器逻辑电路图}
    \label{fig:扭环计数器逻辑电路图}
\end{figure}

普通扭环计数器的逻辑电路结构如图 \ref{fig:普通扭环计数器} 所示\\
其状态循环如图 \ref{fig:扭环计数器状态循环表} 所示，其中第一个表格为正常的状态循环\\
可见，这种扭环计数器是不稳健的


\begin{figure}[htpb]
    \centering
    \begin{subfigure}[t]{0.266\textwidth}
        \begin{center}
        \includegraphics[width=0.99\textwidth]{figures/4位扭环计数器状态循环表.png}
        \end{center}
        \caption{4位扭环计数器状态循环表}
        \label{fig:4位扭环计数器状态循环表}
    \end{subfigure}
    \qquad
    \begin{subfigure}[t]{0.55\textwidth}
        \begin{center}
        \includegraphics[width=0.99\textwidth]{figures/5位扭环计数器状态循环表.png}
        \end{center}
        \caption{5位扭环计数器状态循环表}
        \label{fig:5位扭环计数器状态循环表}
    \end{subfigure}
    \caption{扭环计数器状态循环表}
    \label{fig:扭环计数器状态循环表}
\end{figure}

\begin{quote}
    对 $n$ 位普通扭环计数器，任意初始状态 $A_{n-1}A_{n-2}\cdots A_1A_0$\\
    在 $n$ 次移位后变为 $A_{n-1}'A_{n-2}'\cdots A_1'A_0'$，再经过 $n$ 次移位回归初始状态
\end{quote}

可自校正的扭环计数器电路结构如图 \ref{fig:自校正扭环计数器} 所示\\
其校正方式为：若现态为 $\rm 0x\cdots x0$ 则次态为 $00\cdots01$\\
正常的状态循环正常工作，其它状态循环被打断并回归正常循环

\begin{quote}
    所有不能写为 $\rm x\cdots 10x\cdots x$ 的状态都属于正常状态，故异常状态都可写为 $\rm x\cdots 10x\cdots x$\\
    因此所有异常循环都包含 $\rm 10x\cdots x$，也都包含 $0x\cdots x0$\\
    综上，所使用的校正方式可以打断所有的异常状态循环
\end{quote}

\paragraph{线性反馈移位寄存器型计数器}
线性反馈移位寄存器(LFSR)型计数器也称最大长度序列发生器，基于数学中的有限域理论\\
$n$ 位LFSR有 $2^n-1$ 种正常状态，仅全0状态为异常状态\\
LFSR的状态循环通常可视为“伪随机数”

普通LFSR的逻辑电路结构如图 \ref{fig:普通LFSR逻辑电路图} 所示，其全0状态是自循环的，因此稳健性不佳\\
反馈方程由有限域理论提供，部分列举见表 \ref{tab:n位LFSR的反馈方程列举}

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.8\textwidth]{figures/普通LFSR逻辑电路图.png}
    \caption{普通LFSR逻辑电路图}
    \label{fig:普通LFSR逻辑电路图}
\end{figure}

\begin{table}[htpb]
    \centering
    \caption{n位LFSR的反馈方程列举}
    \label{tab:n位LFSR的反馈方程列举}
    \includegraphics[width=0.35\textwidth]{figures/n位LFSR反馈方程.png}
\end{table}

$n$ 位自校正LFSR的状态循环包含了全部 $2^n$ 个状态\\
校正电路由一个 $n-1$ 输入或非门和一个异或门组成，或非门的输入为 $X_1,\cdots,X_{n-1}$\\
$n=3$ 时的逻辑电路如图 \ref{fig:自校正LFSR逻辑电路图} 所示，状态循环如表 \ref{tab:自校正LFSR状态循环表} 所示

\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.9\textwidth]{figures/自校正LFSR逻辑电路图.png}
    \caption{自校正LFSR逻辑电路图}
    \label{fig:自校正LFSR逻辑电路图}
\end{figure}

\begin{table}[htpb]
    \centering
    \caption{3位自校正LFSR状态循环表}
    \label{tab:自校正LFSR状态循环表}
    \includegraphics[width=0.45\textwidth]{figures/自校正LFSR状态循环表.png}
\end{table}



